2022/11/01 by Wang, Jing, Luan, Xidao, Huang, Yuanqiu
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2211.00320
The generalized k-connectivity of a graph G, denoted by κk(G), is the minimum number of internally edge disjoint S-trees for any S⊆ V(G) with |S|=k. The generalized k-connectivity is a natural extension of the classical connectivity and plays a key role in applications related to the modern interconnection networks. In this paper, we firstly introduce a family of regular networks Hn that can be obtained from several subgraphs Gn1, Gn2, ⋯, Gntn by adding a matching, where each subgraph Gni is isomorphic to a particular graph Gn (1≤ i≤ tn). Then we determine the generalized 3-connectivity of Hn. As applications of the main result, the generalized 3-connectivity of some two-level interconnection networks, such as the hierarchical star graph HSn, the hierarchical cubic network HCNn and the hierarchical folded hypercube HFQn, are determined directly.