Minimal regular graphs with given girths and crossing numbers

• Autorzy: G.L. Chia , C.S. Gan
• Języki publikacji: EN

Abstrakty

EN

This paper investigates on those smallest regular graphs with given girths and having small crossing numbers.

Słowa kluczowe

EN

regular graphs; girth; crossing numbers

Kategorie tematyczne

• 05C35: Extremal problems
• 05C10: Planar graphs; geometric and topological aspects of graph theory
• 05C38: Paths and cycles

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2004
• Tom: 24
• Numer: 2
• Strony: 223-237

Daty

wydano

2004

Twórcy

autor

G.L. Chia

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

autor

C.S. Gan

• Faculty of Engineering and Technology, Multimedia University, 75450 Malacca, Malaysia

Bibliografia

• [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 $K_{5,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.html.
• [11] P.K. Wong, Cages - a survey, J. Graph Theory 6 (1982) 1-22, doi: 10.1002/jgt.3190060103.

Identyfikatory

DOI

10.7151/dmgt.1227