The Generalized Three-Connectivity of Two Kinds of Cayley Graphs. (26th May 2018) - Zhao, Shu-Li; Hao, Rong-Xia
Abstract: Let S ⊆ V ( G ) and κ G ( S ) denote the maximum number r of edge-disjoint trees T 1, T 2, …, T r in G such that V ( T i ) ∩ V ( T j ) = 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 C T n and W G n, respectively. We study the generalized 3-connectivity of the two kinds of graphs and show that κ 3 ( C T n ) = n ( n − 1 ) 2 − 1 and κ 3 ( W G n ) = 2 n − 3 for n ≥ 3 .