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

详细信息    查看全文

• 作者：Jianhua Tu ^{tujh81@163.com} ; Yukang Zhou ^{yukangzhou@126.com} ; Guifu Su ; ^{gfs1983@126.com} ; ^{gfs86@uga.edu}
• 关键词：Wheel graph ; Fault tolerance ; Cayley graph ; Conditional connectivity
• 刊名：Applied Mathematics and Computation
• 出版年：2017
• 出版时间：15 May 2017
• 年：2017
• 卷：301
• 期：Complete
• 页码：177-186
• 全文大小：941 K
• 卷排序：301

文摘

For a connected graph G=(V,E),G=(V,E), a subset F ⊆ V is called an Rk-vertex-cut of G   if G−FG−F is disconnected and each vertex in V−FV−F has at least k   neighbors in G−FG−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}{1,2,…,n} and TT be a set of transpositions of Sym(n  ). Denote by G(T)G(T) the graph with vertex set {1,2,…,n}{1,2,…,n} and edge set {ij:(ij)∈T}{ij:(ij)∈T}. If G(T)G(T) is a wheel graph, then simply denote the Cayley graph Cay(Sym(n),T)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κ1(WGn)=4n−6 and κ2(WGn)=8n−18κ2(WGn)=8n−18.