A note on the upper bound and girth pair of (k; g)-cages

作者：Balbuena C; Gonzalez Moreno D^*; Montellano Ballesteros J J

来源：Discrete Applied Mathematics, 2013, 161(6): 853-857.

DOI：10.1016/j.dam.2012.10.008

• Cage
• Girth pair
• Kronecker product

A (k; g)-cage is a k-regular graph of girth g with minimum order. In this work, for all k %26gt;= 3 and g %26gt;= 5 odd, we present an upper bound of the order of a (k; g + 1)-cage in terms of the order of a (k; g)-cage, improving a previous result by Sauer of 1967. We also show that every (k; 11)-cage with k %26gt;= 6 contains a cycle of length 12, supporting a conjecture by Harary and Kovacs of 1983.

• 出版日期2013-4