Constructions of bi-regular cages

Given three positive integers r , m and g , one interesting question is the following: What is the minimum number of vertices that a graph with prescribed degree set { r , m } , 2 ≤ r < m , and girth g can have? Such a graph is called a bi-regular cage or an ( { r , m } ; g ) -cage, and its minimum order is denoted by n ( { r , m } ; g ) . In this paper we provide new upper bounds on n ( { r , m } ; g ) for some related values of r and m . Moreover, if r − 1 is a prime power, we construct the following bi-regular cages: ( { r , k ( r − 1 ) } ; g ) -cages for g ∈ { 5 , 7 , 11 } and k ≥ 2 even; and ( { r , k r } ; 6 ) -cages for k ≥ 2 any integer. The latter cages are of order n ( { r , k r } ; 6 ) = 2 ( k r 2 − k r + 1 ) . Then this result supports the conjecture that n ( { r , m } ; 6 ) = 2 ( r m − m + 1 ) for any r < m , posed by Yuansheng and Liang [Y. Yuansheng, W. Liang, The minimum number of vertices with girth 6 and degree set D = { r , m } , Discrete Math. 269 (2003) 249–258]. We finalize giving the exact value n ( { 3 , 3 k } ; 8 ) , for k ≥ 2 .