On the order of graphs with a given girth pair

A ( k ; g , h ) -graph is a k -regular graph of girth pair ( g , h ) where g is the girth of the graph, h is the length of a smallest cycle of different parity than g and g < h . A ( k ; g , h ) -cage is a ( k ; g , h ) -graph with the least possible number of vertices denoted by n ( k ; g , h ) . In this paper we give a lower bound on n ( k ; g , h ) and as a consequence we establish that every ( k ; 6 ) -cage is bipartite if it is free of odd cycles of length at most 2 k − 1 . This is a contribution to the conjecture claiming that every ( k ; g ) -cage with even girth g is bipartite. We also obtain upper bounds on the order of ( k ; g , h ) -graphs with g = 6 , 8 , 12 . From the proofs of these upper bounds we obtain a construction of an infinite family of small ( k ; g , h ) -graphs. In particular, the ( 3 ; 6 , h ) -graphs obtained for h = 7 , 9 , 11 are minimal.