A lower bound on the order of regular graphs with given girth pair

✍ Scribed by C. Balbuena; T. Jiang; Y. Lin; X. Marcote; M. Miller

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 129 KB
• Volume: 55
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20230

✦ Synopsis

Abstract

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 (3__g__ − 3)/2. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 153–163, 2007