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 (k;g)-graph is a k-regular graph with girth g. A (k;g)-cage is a (k;g)-graph with the least possible number of vertices. Let f(k;g) denote the number of vertices in a (k;g)-cage. The girth pair of a graph gives the ...A (k;g)-graph is a k-regular graph with girth g. A (k;g)-cage is a (k;g)-graph with the least possible number of vertices. Let f(k;g) denote the number of vertices in a (k;g)-cage. The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. A fc-regular graph with girth pair (g,h) is called a (k;g,h)-graph. A (k;g,h)-cage is a (k;g,h)-graph with the least possible number of vertices. Let f(k;g,h) denote the number of vertices in a (k;g,h)-cage. In this paper, we prove the following strict inequality f(k;h-1,h)<f(k,h), k≥3, h≥4.展开更多
文摘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.
基金the National Natural Science Foundation of China.
文摘A (k;g)-graph is a k-regular graph with girth g. A (k;g)-cage is a (k;g)-graph with the least possible number of vertices. Let f(k;g) denote the number of vertices in a (k;g)-cage. The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. A fc-regular graph with girth pair (g,h) is called a (k;g,h)-graph. A (k;g,h)-cage is a (k;g,h)-graph with the least possible number of vertices. Let f(k;g,h) denote the number of vertices in a (k;g,h)-cage. In this paper, we prove the following strict inequality f(k;h-1,h)<f(k,h), k≥3, h≥4.
