PDF
Discussiones Mathematicae Graph Theory 24(2) (2004)
223-237
DOI: https://doi.org/10.7151/dmgt.1227
MINIMAL REGULAR GRAPHS WITH GIVEN GIRTHS AND CROSSING NUMBERS
G.L. Chia
Institute of Mathematical Sciences |
C.S. Gan
Faculty of Engineering and Technology |
Abstract
This paper investigates on those smallest regular graphs with given girths and having small crossing numbers.Keywords: regular graphs, girth, crossing numbers.
2000 Mathematics Subject Classification: 05C10, 05C35, 05C38.
References
[1] | G. Chartrand and L. Lesniak, Graphs & Digraphs (Third edition), (Chapman & Hall, New York 1996). |
[2] | R.K. Guy and A. Hill, The crossing number of the complement of a circuit, Discrete Math. 5 (1973) 335-344, doi: 10.1016/0012-365X(73)90127-1. |
[3] | D.J. Kleitman, The crossing number of K5,n, J. Combin. Theory B 9 (1970) 315-323, doi: 10.1016/S0021-9800(70)80087-4. |
[4] | M. Koman, On nonplanar graphs with minimum number of vertices and a given girth, Commentationes Math. Univ. Carolinae (Prague) 11 (1970) 9-17. |
[5] | D. McQuillan and R.B. Richter, On 3-regular graphs having crossing number at least 2, J. Graph Theory, 18 (1994) 831-839, doi: 10.1002/jgt.3190180807. |
[6] | M. Nihei, On the girths of regular planar graphs, Pi Mu Epsilon J. 10 (1995) 186-190. |
[7] | B. Richter, Cubic graphs with crossing number two, J. Graph Theory 12 (1988) 363-374, doi: 10.1002/jgt.3190120308. |
[8] | R.D. Ringeisen and L.W. Beineke, 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. |
[9] | G.F. Royle, Graphs and multigraphs, in: C.J. Colbourn and J.H. Dinitz ed., The CRC Handbook of Combinatorial Designs, (CRC Press, New York, 1995) 644-653. |
[10] | G.F. Royle, Cubic cages, http://www.cs.uwa.edu.au/~gordon/cages/index.hmtl. |
[11] | P.K. Wong, Cages - a survey, J. Graph Theory 6 (1982) 1-22, doi: 10.1002/jgt.3190060103. |
Received 24 June 2002
Revised 22 September 2003
Close