The crossing numbers of products of a 5-vertex graph with paths and cycles
Marián Klešč
Discussiones Mathematicae Graph Theory, Tome 19 (1999), p. 59-69 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 1999-01-01
EUDML-ID : urn:eudml:doc:270306 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1085,
     author = {Mari\'an Kle\v s\v c},
     title = {The crossing numbers of products of a 5-vertex graph with paths and cycles},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {19},
     year = {1999},
     pages = {59-69},
     zbl = {0949.05018},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1085}
}

Marián Klešč. The crossing numbers of products of a 5-vertex graph with paths and cycles. Discussiones Mathematicae Graph Theory, Tome 19 (1999) pp. 59-69. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1085/

[000] [1] D. Archdeacon, R.B. Richter, On the parity of crossing numbers, J. Graph Theory 12 (1988) 307-310, doi: 10.1002/jgt.3190120302. | Zbl 0659.05043

[001] [2] 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. | Zbl 0403.05037

[002] [3] F. Harary, Graph Theory (Addison - Wesley, Reading, MA, 1969).

[003] [4] S. Jendrol', M. S cerbová, On the crossing numbers of Sₘ × Pₙ and Sₘ × Cₙ, Casopis pro pestování matematiky 107 (1982) 225-230.

[004] [5] M. Klešč, On the crossing numbers of Cartesian products of stars and paths or cycles, Mathematica Slovaca 41 (1991) 113-120. | Zbl 0755.05067

[005] [6] M. Klešč, The crossing numbers of products of paths and stars with 4-vertex graphs, J. Graph Theory 18 (1994) 605-614. | Zbl 0808.05038

[006] [7] M. Klešč, The crossing numbers of certain Cartesian products, Discuss. Math. Graph Theory 15 (1995) 5-10, doi: 10.7151/dmgt.1001. | Zbl 0828.05028

[007] [8] M. Klešč, The crossing number of K2,3×Pₙ and K2,3×Sₙ, Tatra Mountains Math. Publ. 9 (1996) 51-56.

[008] [9] M. Klešč, R.B. Richter, I. Stobert, The crossing number of C₅ × Cₙ, J. Graph Theory 22 (1996) 239-243. | Zbl 0854.05036

[009] [10] A.T. White, L.W. Beineke, Topological graph theory, in: Selected Topics in Graph Theory (Academic Press, London, 1978) 15-49.