A Kind of Conditional Connectivity of Cayley Graphs Generated by 2-trees. (25th October 2017) - Xu, Liqiong; Zhou, Shuming; Lian, Guanqin; Luo, Zuwen
Abstract: For a connected graph G = ( V ( G ), E ( G ) ), a subset F ⊂ V ( G ) is called an R k -vertex-cut if G − F is disconnected and each vertex u ∈ V ( G ) − F has at least k neighbors in G − F . The cardinality of a minimum R k -vertex-cut of G is the R k -vertex-connectivity and is denoted by κ k ( G ) . The conditional connectivity is a new measure to study the fault tolerance of network structures beyond connectivity. In this paper, we study R 1 -vertex-connectivity and R 2 -vertex-connectivity of Cayley graphs generated by 2-trees T 2, n, which are denoted by K T n, and show that κ 1 ( K T n ) = 4 n − 8 for n ≥ 4 ; κ 2 ( K T n ) = 8 n − 22 for n ≥ 6 .