Premium
A lower bound on the order of regular graphs with given girth pair
Author(s) -
Balbuena C.,
Jiang T.,
Lin Y.,
Marcote X.,
Miller M.
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20230
Subject(s) - combinatorics , mathematics , girth (graph theory) , odd graph , upper and lower bounds , graph , discrete mathematics , conjecture , cubic graph , cage , line graph , voltage graph , pathwidth , mathematical analysis
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