A kind of conditional connectivity of Cayley graphs generated by unicyclic graphs
For a graph G=(V, E), a subset F?V(G) is called an Rk-vertex-cut of G if G?F is disconnected and each vertex u?V(G)?F has at least k neighbors in G?F. The Rk-vertex-connectivity of G, denoted by ?k(G), is the cardinality of the minimum Rk-vertex-cut of G, which is a refined measure for the fault tolerance of network G. In this paper, we study ?2 for Cayley graphs generated by unicyclic graphs. Let Sym(n) be the symmetric group on {1,2,,n } and T T be a set of transpositions of Sym(n ). Let G(T) G ( T ) be the graph on vertex set {1,2,,n } and edge set {ij:(ij)?T} { ij : ( ij ) ? T } . If G(T) G ( T ) is a unicyclic graph, then simply denote the Cayley graph Cay(Sym(n),T) Cay ( Sym ( n ) , T ) by UGn. In particular, if G(T) G ( T ) is a cycle, then UGn is the well-known modified bubble sort graph MBn. We prove in this paper that if m  is the length of the unique cycle in G(T) G ( T ) , then
conditional connectivity unicyclic graph fault tolerance modified bubble sort graph caylay graph