A (δ, g)-cage is a δ-regular graph with girth g and with the least possible number of vertices. In this paper, we show that all (δ, g)-cages with odd girth g ≥ 9 are r-connected, where (r - 1)2 ≤δ + x/δ ...A (δ, g)-cage is a δ-regular graph with girth g and with the least possible number of vertices. In this paper, we show that all (δ, g)-cages with odd girth g ≥ 9 are r-connected, where (r - 1)2 ≤δ + x/δ - 2 〈 r2 and all (δ, g)-cages with even girth g 〉 10 are r-connected, where r is the largest integer satisfying r(r-1)2/4 + 1 + 2r(r - 1) ≤δ. These results support a conjecture of Fkl, Huang and Rodger that all (δ, g)-cages are 6-connected.展开更多
文摘A (δ, g)-cage is a δ-regular graph with girth g and with the least possible number of vertices. In this paper, we show that all (δ, g)-cages with odd girth g ≥ 9 are r-connected, where (r - 1)2 ≤δ + x/δ - 2 〈 r2 and all (δ, g)-cages with even girth g 〉 10 are r-connected, where r is the largest integer satisfying r(r-1)2/4 + 1 + 2r(r - 1) ≤δ. These results support a conjecture of Fkl, Huang and Rodger that all (δ, g)-cages are 6-connected.