Download PDF - The projective plane crossing number of the circulant graph C(3k;{1,k})All rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

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

Authors 1

Affiliations

  1. Department of Mathematics, Sogang University, Seoul 121-742, Korea

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

ENG
crossing number, circulant graph, projective plane

Bibliography

  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 K₉, Discrete Math. 145 (1995) 211-227, doi: 10.1016/0012-365X(94)00037-J.
  19. A. Riskin, The projective plane crossing number of C₃ × Cₙ, 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.
Discussiones Mathematicae Graph Theory
2012/32/1
Export to PBN, Opens in new tab
Pages:
91-108
Main language of publication
English
Received
2010-09-02
Accepted
2011-01-26
Published
2012

DOI: 10.7151/dmgt.1588

Exact and natural sciences