On a conjecture on the order of cages with a given girth pair
A (k;g,h) ( k ; g , h ) -graph is a k k -regular graph of girth pair (g,h) ( g , h ) where g g is the girth of the graph, h h is the length of a smallest cycle of different parity than g g and g<h g < h . A (k;g,h) ( k ; g , h ) -cage is a (k;g,h) ( k ; g , h ) -graph with the least possible number of vertices denoted n(k;g,h) n ( k ; g , h ) . Harary and Kvacs (1983) conjectured the inequality n(k;g,h)?n(k,h) n ( k ; g , h ) ? n ( k , h ) for all k?3 k ? 3 , g?3 g ? 3 , h?g+1 h ? g + 1 . In this paper, we prove this conjecture for all (k;g,h) ( k ; g , h ) -cage with g g odd provided that a bipartite (k,h) ( k , h ) -cage exists. When g g is even we prove the conjecture for h?2g?1 h ? 2 g ? 1 , provided that a bipartite (k,g) ( k , g ) -cage exists.
cages girth pair regular graph