The projective plane crossing number of the circulant graph C(3k;{1,k})

Pak Tung Ho

Discussiones Mathematicae Graph Theory, Tome 32 (2012), p. 91-108 / Harvested from The Polish Digital Mathematics Library

Résumé

In this paper we prove that the projective plane crossing number of the circulant graph C(3k;{1,k}) is k-1 for k ≥ 4, and is 1 for k = 3.

Détail

Publié le : 2012-01-01

Zbl 1255.05055

EUDML-ID : urn:eudml:doc:270982

Bibliographie

[000] [1] S.N. Bhatt and F.T. Leighton, A framework for solving VLSI graph layout problems, J. Comput. System Sci. 28 (1984) 300-343, doi: 10.1016/0022-0000(84)90071-0. | Zbl 0543.68052

[001] [2] P. Erdös, and R.K. Guy, Crossing number problems, Amer. Math. Monthly 80 (1973) 52-58, doi: 10.2307/2319261. | Zbl 0264.05109

[002] [3] M.R. Garey and D.S. Johnson, Crossing number is NP-complete, SIAM J. Algebraic Discrete Methods 1 (1983) 312-316, doi: 10.1137/0604033. | Zbl 0536.05016

[003] [4] R.K. Guy and T.A. Jenkyns, The toroidal crossing number of $K_{m,n}$, J. Combin. Theory 6 (1969) 235-250, doi: 10.1016/S0021-9800(69)80084-0. | Zbl 0176.22303

[004] [5] R.K. Guy, T. Jenkyns and J. Schaer, The toroidal crossing number of the complete graph, J. Combin. Theory 4 (1968) 376-390, doi: 10.1016/S0021-9800(68)80063-8. | Zbl 0172.48804

[005] [6] P. Hliněný, Crossing number is hard for cubic graphs, J. Combin. Theory (B) 96 (2006) 455-471, doi: 10.1016/j.jctb.2005.09.009. | Zbl 1092.05016

[006] [7] P.T. Ho, A proof of the crossing number of $K_{3,n}$ in a surface, Discuss. Math. Graph Theory 27 (2007) 549-551, doi: 10.7151/dmgt.1379. | Zbl 1142.05018

[007] [8] P.T. Ho, The crossing number of C(3k+1;{1,k}), Discrete Math. 307 (2007) 2771-2774, doi: 10.1016/j.disc.2007.02.001. | Zbl 1129.05012

[008] [9] P.T. Ho, The crossing number of $K_{4,n}$ on the projective plane, Discrete Math. 304 (2005) 23-34, doi: 10.1016/j.disc.2005.09.010. | Zbl 1079.05026

[009] [10] P.T. Ho, The toroidal crossing number of $K_{4,n}$, Discrete Math. 309 (2009) 3238-3248, doi: 10.1016/j.disc.2008.09.029. | Zbl 1177.05032

[010] [11] D.J. Kleitman, The crossing number of $K_{5,n}$, J. Combin. Theory 9 (1970) 315-323, doi: 10.1016/S0021-9800(70)80087-4. | Zbl 0205.54401

[011] [12] X. Lin, Y. Yang, J. Lu and X. Hao, The crossing number of C(mk;{1,k}), Graphs Combin. 21 (2005) 89-96, doi: 10.1007/s00373-004-0597-5. | Zbl 1061.05027

[012] [13] X. Lin, Y. Yang, J. Lu and X. Hao, The crossing number of C(n;{1,⌊ n/2⌋-1}), Util. Math. 71 (2006) 245-255. | Zbl 1109.05035

[013] [14] D. Ma, H. Ren and J. Lu, The crossing number of the circular graph C(2m+2,m), Discrete Math. 304 (2005) 88-93, doi: 10.1016/j.disc.2005.04.018. | Zbl 1077.05033

[014] [15] B. Mohar and C. Thomassen, Graphs on Surfaces (Johns Hopkins University Press, Baltimore, 2001).

[015] [16] S. Pan and R.B. Richter, The crossing number of $K_{11}$ is 100, J. Graph Theory 56 (2007) 128-134, doi: 10.1002/jgt.20249. | Zbl 1128.05018

[016] [17] R.B. Richter and J. Širáň, The crossing number of $K_{3,n}$ in a surface, J. Graph Theory 21 (1996) 51-54, doi: 10.1002/(SICI)1097-0118(199601)21:1<51::AID-JGT7>3.0.CO;2-L | Zbl 0838.05033

[017] [18] A. Riskin, The genus 2 crossing number of K₉, Discrete Math. 145 (1995) 211-227, doi: 10.1016/0012-365X(94)00037-J. | Zbl 0833.05027

[018] [19] A. Riskin, The projective plane crossing number of C₃ × Cₙ, J. Graph Theory 17 (1993) 683-693, doi: 10.1002/jgt.3190170605. | Zbl 0794.05021

[019] [20] G. Salazar, On the crossing numbers of loop networks and generalized Petersen graphs, Discrete Math. 302 (2005) 243-253, doi: 10.1016/j.disc.2004.07.036. | Zbl 1080.05026

[020] [21] L.A. Székely, A successful concept for measuring non-planarity of graphs: the crossing number, Discrete Math. 276 (2004) 331-352, doi: 10.1016/S0012-365X(03)00317-0. | Zbl 1035.05034

[021] [22] D.R. Woodall, Cyclic-order graphs and Zarankiewicz's crossing number conjecture, J. Graph Theory 17 (1993) 657-671, doi: 10.1002/jgt.3190170602. | Zbl 0792.05142

[022] [23] Y. Yang, X. Lin, J. Lu and X. Hao, The crossing number of C(n;{1,3}), Discrete Math. 289 (2004) 107-118, doi: 10.1016/j.disc.2004.08.014. | Zbl 1056.05043