The connectivity is an important measurement for the fault tolerance of a network. Let G = (V(G), E(G)) be a connected graph with the vertex set V(G) and edge set E(G). An S‐tree of graph G is a tree T that contains all the vertices in S subject to S⊆V(G). Two S‐trees T and T′ are internally disjoint if and only if E(T)∩E(T′) = ∅ and V(T)∩V(T′) = S. Denote κG(S) by the maximum number of internally disjoint S‐trees in graph G. The generalized k‐connectivity is a natural generalization of the classical connectivity, which is defined as κr(G) = min{κG(S)|S⊆V(G)and|S| = r}. In this paper, we mainly focus on the generalized connectivity of cube‐connected‐cycle CCCn and hierarchical hypercube HHCn, which were introduced for massively parallel systems. We show that for n = 2m + 2(m ≥ 1), κ4(HHCn) = m and κ4(CCCn) = 2, that is, for any four vertices in CCCn (or HHCn), there exist 2 (or m) internally disjoint S‐trees connecting them in CCCn (or HHCn).
1 January 2022 in Discrete Dynamics in Nature and Society
A supertree is a connected and acyclic hypergraph. Denote by Tm,n,α the set of m‐uniform supertrees of order n with independent number α. Focusing on the spectral radius in Tm,n,α, this present completely determines the hypergraphs with maximum spectral radius among all the supertrees with n vertices and independence number α for [m − 1/mn] ≤ α ≤ n − 1, which extend the results of Lu et al. from tree to uniform supertree. Our techniques are based on the structure properties of supertrees with given independence number and general edge‐moving operation. As a byproduct, we also determine the hypergraphs with minimum signless Laplacian spectral radius in Tm,n,α.