Loading...
Loading...

Go to the content (press return)

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

Author
Balbuena, C.; González, D.; Montellano-Ballesteros, J.J.
Type of activity
Journal article
Journal
Discrete applied mathematics
Date of publication
2013-04
Volume
161
Number
6
First page
853
Last page
857
DOI
https://doi.org/10.1016/j.dam.2012.10.008 Open in new window
Abstract
A (k;g)(k;g)-cage is a kk-regular graph of girth gg with minimum order. In this work, for all k=3k=3 and g=5g=5 odd, we present an upper bound of the order of a (k;g+1)(k;g+1)-cage in terms of the order of a (k;g)(k;g)-cage, improving a previous result by Sauer of 1967. We also show that every (k;11)(k;11)-cage with k=6k=6 contains a cycle of length 12, supporting a conjecture by Harary and Kovács of 1983.
Keywords
Cage, Girth pair, Kronecker product
Group of research
COMBGRAPH - Combinatorics, Graph Theory and Applications

Participants