A kind of conditional connectivity of Cayley graphs generated by wheel graphs

作者：Tu, Jianhua; Zhou, Yukang; Su, Guifu^*

来源：Applied Mathematics and Computation, 2017, 301: 177-186.

DOI：10.1016/j.amc.2016.12.015

• Wheel graph
• Fault tolerance
• Cayley graph
• Conditional connectivity

For a connected graph G = (V, E), a subset F subset of V is called an R-k-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 R-k-vertex-cut is the R-k-vertex-connectivity of G and is denoted by kappa(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) is an element of T}. If G(T) is a wheel graph, then simply denote the Cayley graph Cay(Sym(n), T) by WG(n). In this paper, we determine the values of kappa(1) and kappa(2) for Cayley graphs generated by wheel graphs and prove that kappa(1)(WG(n)) = 4n - 6 and k(2)(WG(n)) = 8n - 18.

• 出版日期2017-5-15
• 单位北京化工大学