Title: The generalized <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e897" altimg="si41.svg"><mml:mn>3</mml:mn></mml:math>-connectivity of some Regular Networks
Abstract: For a vertex set S with cardinality at least two, we need a tree to connect them, where this tree is usually called an S-Steiner tree (or a tree connecting S). Two S-Steiner trees T and T′ are said to be internally disjoint if E(T)∩E(T′)=0̸ and V(T)∩V(T′)=S. Let κG(S) denote the maximum number r of internally disjoint S-Steiner trees in G. 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}. It is proved NP-complete to determine κk(G) for a general graph G. So far, the exact values of κk(G) are known for small classes of graphs and most of them are about k=3. In this paper, we introduce a family of m-regular and m-connected graph Gn which are constructed recursively and contains many important interconnection networks such as the alternating group graph AGn, the k-ary n-cube Qnk, the split-star network Sn2 and the bubble-sort-star graph BSn. We study the generalized 3-connectivity of Gn and show that κ3(Gn)=m−1, which attains the upper bound of κ3(G) given by Li et al. for G=Gn. As applications, the generalized 3-connectivity of AGn, Qnk, Sn2 and BSn etc., can be obtained directly.
Publication Year: 2019
Publication Date: 2019-11-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 21
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot