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 is an element of {5, 7, 11} and k >= 2 even; and ({r, kr}; 6)-cages for k >= 2 any integer. The latter cages are of order n({r, kr}; 6) = 2(kr(2) - kr + 1). Then this result supports the conjecture that n({r, m}; 6) = 2(rm - 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, 3k}; 8), for k >= 2. (C) 2008 Elsevier B.V. All rights reserved.