Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/926782
- Title
- A lower bound on the order of regular graphs with given girth pair
- Author/Creator
-
Balbuena, C.;
Jiang, T.;
Lin, Y.;
Marcote, X.;
Miller, M.
- Institution
- The University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science
- Description
- The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair was proved by Harary and Kovács [Regular graphs with given girth pair, J Graph Theory 7 (1983), 209–218]. A (δ, g)-cage is a smallest δ-regular graph with girth g. For all δ ≥ 3 and odd girth g ≥ 5, Harary and Kovács conjectured the existence of a (δ,g)-cage that contains a cycle of length g + 1. In the main theorem of this article we present a lower bound on the order of a δ-regular graph with odd girth g ≥ 5 and even girth h ≥ g + 3. We use this bound to show that every (δ,g)-cage with δ ≥ 3 and g ∈ {5,7} contains a cycle of length g + 1, a result that can be seen as an extension of the aforementioned conjecture by Harary and Kovács for these values of δ, g. Moreover, for every odd g ≥ 5, we prove that the even girth of all (δ,g)-cages with δ large enough is at most (3g − 3)/2.
- Relation
- Journal of Graph Theory Vol. 55, Issue 2, p. 153-163
- Publisher Link
- http://dx.doi.org/10.1002/jgt.20230
- Date
- 2007
- Publisher
- John Wiley & Sons
- Keyword(s)
-
cages;
connectivity;
girth pairs
- Resource Type
- journal article
- Identifier
- http://hdl.handle.net/1959.13/926782
- Identifier
- ISSN:0364-9024
- Reviewed
7 Visitors
10 Hits
0 Downloads
