Geodesic
On the crossing numbers of G □ Cₙ for graphs G on six vertices
Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 2, pp. 239-252.

Voir la notice de l'article provenant de la source Library of Science

The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. The crossing numbers of G☐Cₙ for some graphs G on five and six vertices and the cycle Cₙ are also given. In this paper, we extend these results by determining crossing numbers of Cartesian products G☐Cₙ for some connected graphs G of order six with six and seven edges. In addition, we collect known results concerning crossing numbers of G☐Cₙ for graphs G on six vertices.
Keywords: graph, cycle, drawing, crossing number, Cartesian product 
@article{DMGT_2011_31_2_a2,
     author = {Dra\v{z}ensk\'a, Em{\'\i}lia and Kle\v{s}\v{c}, Mari\'an},
     title = {On the crossing numbers of {G} \ensuremath{\square} {Cₙ} for graphs {G} on six vertices},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {239--252},
     publisher = {mathdoc},
     volume = {31},
     number = {2},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2011_31_2_a2/}
}
TY  - JOUR
AU  - Draženská, Emília
AU  - Klešč, Marián
TI  - On the crossing numbers of G □ Cₙ for graphs G on six vertices
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2011
SP  - 239
EP  - 252
VL  - 31
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2011_31_2_a2/
LA  - en
ID  - DMGT_2011_31_2_a2
ER  - 
%0 Journal Article
%A Draženská, Emília
%A Klešč, Marián
%T On the crossing numbers of G □ Cₙ for graphs G on six vertices
%J Discussiones Mathematicae. Graph Theory
%D 2011
%P 239-252
%V 31
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2011_31_2_a2/
%G en
%F DMGT_2011_31_2_a2
Draženská, Emília; Klešč, Marián. On the crossing numbers of G □ Cₙ for graphs G on six vertices. Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 2, pp. 239-252. http://geodesic.mathdoc.fr/item/DMGT_2011_31_2_a2/

[1] M. Anderson, R.B. Richter and P. Rodney, The crossing number of C₆×C₆, Congr. Numer. 118 (1996) 97-107.

[2] L.W. Beineke and 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.

[3] A.M. Dean and R.B. Richter, The crossing number of C₄×C₄, J. Graph Theory 19 (1995) 125-129, doi: 10.1002/jgt.3190190113.

[4] E. Draženská and M. Klešč, The crossing numbers of products of cycles with 6-vertex trees, Tatra Mt. Math. Publ. 36 (2007) 109-119.

[5] E. Draženská, The crossing numbers of G☐Cₙ for the graph G on six vertices, Mathematica Slovaca (to appear).

[6] L.Y. Glebsky and G. Salazar, The crossing number of Cₘ×Cₙ is as conjectured for n ≥ m(m+1), J. Graph Theory 47 (2004) 53-72, doi: 10.1002/jgt.20016.

[7] F. Harary, P.C. Kainen and A.J. Schwenk, Toroidal graphs with arbitrarily high crossing numbers, Nanta Math. 6 (1973) 58-67.

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

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

[10] M. Klešč, The crossing numbers of Cartesian products of paths with 5-vertex graphs, Discrete Math. 233 (2001) 353-359, doi: 10.1016/S0012-365X(00)00251-X.

[11] M. Klešč, The crossing number of $K_{2,3}×C₃$, Discrete Math. 251 (2002) 109-117, doi: 10.1016/S0012-365X(01)00332-6.

[12] M. Klešč, Some crossing numbers of products of cycles, Discuss. Math. Graph Theory 25 (2005) 197-210, doi: 10.7151/dmgt.1272.

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

[14] M. Klešč and A. Kocúrová, The crossing numbers of products of 5-vertex graphs with cycles, Discrete Math. 307 (2007) 1395-1403, doi: 10.1016/j.disc.2005.11.077.

[15] R.B. Richter and C. Thomassen, Intersection of curve systems and the crossing number of C₅×C₅, Discrete Comp. Geom. 13 (1995) 149-159, doi: 10.1007/BF02574034.

[16] R.B. Richter and G. Salazar, The crossing number of C₆×Cₙ, Australasian J. Combin. 23 (2001) 135-144.

[17] R D. Ringeisen and L.W. Beineke, The crossing number of C₃×Cₙ, J. Combin. Theory (B) 24 (1978) 134-136, doi: 10.1016/0095-8956(78)90014-X.

[18] W. Zheng, X. Lin, Y. Yang and C. Deng, On the crossing number of Kₘ ☐ Cₙ and $K_{m,l} ☐ Pₙ$, Discrete Appl. Math. 156 (2008) 1892-1907.