Article ID Journal Published Year Pages File Type
5775941 Applied Mathematics and Computation 2017 10 Pages PDF
Abstract
For a connected graph G=(V,E), a subset F ⊆ V is called an Rk-vertex-cut of G if G−F is disconnected and each vertex in V−F has at least k neighbors in G−F. The cardinality of the minimum Rk-vertex-cut is the Rk-vertex-connectivity of G and is denoted by κk(G). The conditional connectivity is a measure to explore the structure of networks beyond the vertex-connectivity. Let Sym(n) be the symmetric group on {1,2,…,n} and T be a set of transpositions of Sym(n). Denote by G(T) the graph with vertex set {1,2,…,n} and edge set {ij:(ij)∈T}. If G(T) is a wheel graph, then simply denote the Cayley graph Cay(Sym(n),T) by WGn. In this paper, we determine the values of κ1 and κ2 for Cayley graphs generated by wheel graphs and prove that κ1(WGn)=4n−6 and κ2(WGn)=8n−18.
Related Topics
Physical Sciences and Engineering Mathematics Applied Mathematics
Authors
, , ,