The crossing numbers of products of a 5-vertex graph with paths and cycles

Marián Klešč

ArticleOriginal scientific text

Title

The crossing numbers of products of a 5-vertex graph with paths and cycles

Authors ¹

Affiliations

Department of Mathematics, Faculty of Electrical Engineering and Informatics, Technical University, 042 00 Košice, Slovak Republic

Abstract

There are several known exact results on the crossing numbers of Cartesian products of paths, cycles or stars with "small" graphs. Let H be the 5-vertex graph defined from K₅ by removing three edges incident with a common vertex. In this paper, we extend the earlier results to the Cartesian products of H × Pₙ and H × Cₙ, showing that in the general case the corresponding crossing numbers are 3n-1, and 3n for even n or 3n+1 if n is odd.

Keywords

ENG

graph, drawing, crossing number, path, cycle, Cartesian product

D. Archdeacon, R.B. Richter, On the parity of crossing numbers, J. Graph Theory 12 (1988) 307-310, doi: 10.1002/jgt.3190120302.
L.W. Beineke, R.D. Ringeisen, On the crossing numbers of products of cycles and graphs of order four, J. Graph Theory 4 (1980) 145-155, doi: 10.1002/jgt.3190040203.
F. Harary, Graph Theory (Addison - Wesley, Reading, MA, 1969).
S. Jendrol', M. S cerbová, On the crossing numbers of Sₘ × Pₙ and Sₘ × Cₙ, Casopis pro pestování matematiky 107 (1982) 225-230.
M. Klešč, On the crossing numbers of Cartesian products of stars and paths or cycles, Mathematica Slovaca 41 (1991) 113-120.
M. Klešč, The crossing numbers of products of paths and stars with 4-vertex graphs, J. Graph Theory 18 (1994) 605-614.
M. Klešč, The crossing numbers of certain Cartesian products, Discuss. Math. Graph Theory 15 (1995) 5-10, doi: 10.7151/dmgt.1001.
M. Klešč, The crossing number of $K_{2, 3} \times P ₙ$ and $K_{2, 3} \times S ₙ$ , Tatra Mountains Math. Publ. 9 (1996) 51-56.
M. Klešč, R.B. Richter, I. Stobert, The crossing number of C₅ × Cₙ, J. Graph Theory 22 (1996) 239-243.
A.T. White, L.W. Beineke, Topological graph theory, in: Selected Topics in Graph Theory (Academic Press, London, 1978) 15-49.

Title

The crossing numbers of products of a 5-vertex graph with paths and cycles

Affiliations

Abstract

Keywords

Bibliography