A (D;g)-cage is a graph having the minimum number of vertices, with degree set D and girth g. Denote by f(D;g) the number of vertices in a (D;g)-cage. In this paper it is shown that f({r,m}; 6) ≥ 2(rm - m + 1) for any 2 ≤ r < m, and f({r,m};6) = 2(rm - m + 1) if either (i) 2 ≤ r ≤ 5 and r < m or (ii) m - 1 is a prime power and 2 ≤ r < m. Upon these results it is conjectured that f({r,m};6) = 2(rm - m + 1) for any r with 2 ≤ r < m.
展开▼
