Let G be a k-regular connected graph of order at least six. If G has girth three, its 3-restricted edge connectivity λ3(G) ≤3k-6. The equality holds when G is a cubic or 4-regular connected vertex-transitive graph w...Let G be a k-regular connected graph of order at least six. If G has girth three, its 3-restricted edge connectivity λ3(G) ≤3k-6. The equality holds when G is a cubic or 4-regular connected vertex-transitive graph with the only exception that G is a 4-regular graph with λ3(G) = 4. Furthermore, λ3(G) = 4 if and only if G contains K4 as its subgraph.展开更多
限制弧割是将有向连通图G分割成阶数至少为2的双向连通分支的弧割,有向图G的最小限制弧割的弧数称为图G的限制弧连通度.易见,一个有向图(2,)G B n至少有4个顶点才有限制弧割.本文证明了:当n³7时,二元有向图De Bruijn图是极大限制...限制弧割是将有向连通图G分割成阶数至少为2的双向连通分支的弧割,有向图G的最小限制弧割的弧数称为图G的限制弧连通度.易见,一个有向图(2,)G B n至少有4个顶点才有限制弧割.本文证明了:当n³7时,二元有向图De Bruijn图是极大限制弧连通的.展开更多
Let G be a fc-regular connected vertex transitive graph. If G is not maximal restricted edge connected, then G has a (k- 1)-factor with components isomorphic to the same vertex transitive graph of order between k and ...Let G be a fc-regular connected vertex transitive graph. If G is not maximal restricted edge connected, then G has a (k- 1)-factor with components isomorphic to the same vertex transitive graph of order between k and 2k-3. This observation strenghen to some extent the corresponding result obtained by Watkins, which said that fc-regular vertex transitive graph G has a factor with components isomorphic to a vertex transitive graphs if G is not k connected.展开更多
文摘Let G be a k-regular connected graph of order at least six. If G has girth three, its 3-restricted edge connectivity λ3(G) ≤3k-6. The equality holds when G is a cubic or 4-regular connected vertex-transitive graph with the only exception that G is a 4-regular graph with λ3(G) = 4. Furthermore, λ3(G) = 4 if and only if G contains K4 as its subgraph.
基金Supported by NNSF of China (Grant No. 10271105) Foundation of Education Ministry of Fujian Province (Grant No. AJ03147) Foundation of Science and Technology Ministry of Fujian Province (Grant No. 2003J036)
基金Supported by NNSF of China(10271105) Doctoral Foundation of Zhangzhou Normal College.
文摘Let G be a fc-regular connected vertex transitive graph. If G is not maximal restricted edge connected, then G has a (k- 1)-factor with components isomorphic to the same vertex transitive graph of order between k and 2k-3. This observation strenghen to some extent the corresponding result obtained by Watkins, which said that fc-regular vertex transitive graph G has a factor with components isomorphic to a vertex transitive graphs if G is not k connected.
