The Generalized Three-Connectivity of Two Kinds of Cayley Graphs
Shu-Li Zhao, Rong‐Xia Hao · The Computer Journal · 2018
Let S⊆V(G) and κG(S) denote the maximum number r of edge-disjoint trees T1,T2,…,Tr in G such that V(Ti)∩V(Tj)=S for any i,j∈{1,2,…,r} and i≠j. For an integer k with 2≤k≤n, the generalized k-connectivity of a graph G is defined as κk(G)=min{κG(S)|S⊆V(G) and |S|=k}. The generalized k-connectivity is a generalization of traditional connectivity. In this paper, we focus on the Cayley graph generated by complete graphs and the Cayley graph generated by wheel graphs, denoted by CTn and WGn, respectively. We study the generalized 3-connectivity of the two kinds of graphs and show that κ3(CTn)=n(n−1)2−1 and κ3(WGn)=2n−3 for n≥3.