DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 24(2) (2004) 223-237
DOI: 10.7151/dmgt.1227

MINIMAL REGULAR GRAPHS WITH GIVEN GIRTHS AND CROSSING NUMBERS

G.L. Chia

Institute of Mathematical Sciences
University of Malaya
50603 Kuala Lumpur, Malaysia

C.S. Gan

Faculty of Engineering and Technology
Multimedia University

75450 Malacca, Malaysia

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