2019/08/28 by Shu-Li Zhao, Rong-Xia Hao, Rong‐Xia Hao +2 · 1 citation
Computer Science · Mathematics · #Interconnection Networks and Systems #Graph theory and applications #Advanced Graph Theory Research
paper · doi:10.1093/comjnl/bxz116
Abstract The generalized k-connectivity of a graph G is a parameter that can measure the reliability of a network G to connect any k vertices in G, which is a generalization of traditional connectivity. 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)\bigcap 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\. In this paper, we introduce a family of regular graph Gn that can be constructed recursively and each vertex with exactly one outside neighbor. The generalized 3-connectivity of the regular graph Gn is studied, which attains a previously proven upper bound on κ 3(G). As applications of the main result, the generalized 3-connectivity of some important networks including some known results such as the alternating group network ANn, the star graph Sn and the pancake graphs Pn can be obtained directly.