A Kind of Conditional Connectivity of Cayley Graphs Generated by 2-trees
Liqiong Xu, Shuming Zhou, Guanqin Lian, Zuwen Luo · The Computer Journal · 2017
For a connected graph G=(V(G),E(G)), a subset F⊂V(G) is called an Rk-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 Rk-vertex-cut of G is the Rk-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 R1-vertex-connectivity and R2-vertex-connectivity of Cayley graphs generated by 2-trees T2,n, which are denoted by KTn, and show that κ1(KTn)=4n−8 for n≥4; κ2(KTn)=8n−22 for n≥6.