PDF
Discussiones Mathematicae Graph Theory 32(1) (2012)
91-108
DOI: https://doi.org/10.7151/dmgt.1588
The Projective Plane Crossing Number of the Circulant Graph C(3k;{1,k})
Pak Tung Ho
Department of Mathematics, Sogang University, |
Abstract
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.
Keywords: crossing number, circulant graph, projective plane
2010 Mathematics Subject Classification: 05C10.
References
[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. |
[2] | P. Erdös, and R.K. Guy, Crossing number problems, Amer. Math. Monthly 80 (1973) 52--58, doi: 10.2307/2319261. |
[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. |
[4] | R.K. Guy and T.A. Jenkyns, The toroidal crossing number of Km,n, J. Combin. Theory 6 (1969) 235--250, doi: 10.1016/S0021-9800(69)80084-0. |
[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. |
[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. |
[7] | P.T. Ho, A proof of the crossing number of K3,n in a surface, Discuss. Math. Graph Theory 27 (2007) 549--551, doi: 10.7151/dmgt.1379. |
[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. |
[9] | P.T. Ho, The crossing number of K4,n on the projective plane, Discrete Math. 304 (2005) 23--34, doi: 10.1016/j.disc.2005.09.010. |
[10] | P.T. Ho, The toroidal crossing number of K4,n, Discrete Math. 309 (2009) 3238--3248, doi: 10.1016/j.disc.2008.09.029. |
[11] | D.J. Kleitman, The crossing number of K5,n, J. Combin. Theory 9 (1970) 315--323, doi: 10.1016/S0021-9800(70)80087-4. |
[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. |
[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. |
[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. |
[15] | B. Mohar and C. Thomassen, Graphs on Surfaces (Johns Hopkins University Press, Baltimore, 2001). |
[16] | S. Pan and R.B. Richter, The crossing number of K11 is 100, J. Graph Theory 56 (2007) 128--134, doi: 10.1002/jgt.20249. |
[17] | R.B. Richter and J. Širáň, The crossing number of K3,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. |
[18] | A. Riskin, The genus 2 crossing number of K9, Discrete Math. 145 (1995) 211--227, doi: 10.1016/0012-365X(94)00037-J. |
[19] | A. Riskin, The projective plane crossing number of C3× Cn, J. Graph Theory 17 (1993) 683--693, doi: 10.1002/jgt.3190170605. |
[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. |
[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. |
[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. |
[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. |
Received 2 September 2010
Revised 26 January 2011
Accepted 26 January 2011
Close