- Title
- A lower bound on the order of regular graphs with given girth pair
- Creator
- Balbuena, C.; Jiang, T.; Lin, Y.; Marcote, X.; Miller, M.
- Relation
- Journal of Graph Theory Vol. 55, Issue 2, p. 153-163
- Publisher Link
- http://dx.doi.org/10.1002/jgt.20230
- Publisher
- John Wiley & Sons
- Resource Type
- journal article
- Date
- 2007
- 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.
- Subject
- cages; connectivity; girth pairs
- Identifier
- http://hdl.handle.net/1959.13/926782
- Identifier
- uon:9940
- Identifier
- ISSN:0364-9024
- Language
- eng
- Reviewed
- Hits: 3223
- Visitors: 3518
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|