Packing internally disjoint Steiner trees to compute the κ3-connectivity in augmented cubes

Given a connected graph G and S subset of V(G) with vertical bar S vertical bar >= 2, a tree T in G is called an S-Steiner tree (or S-tree for short) if S subset of V (T). Two S-trees T-1 and T-2 are internally disjoint if E(T-1) boolean AND E(T-2) = empty set and V (T-1) boolean AND V (T-2) = S. The packing number of internally disjoint S-trees, denoted as kappa(G) (S), is the maximum size of a set of internally disjoint S-trees in G. For an integer kappa >= 2, the generalized k-connectivity (abbr. kappa(kappa)-connectivity) of a graph G is defined as kappa(kappa) (G) = min{kappa(G) (S) vertical bar S subset of V (G) and vertical bar S vertical bar = kappa}. The n-dimensional augmented cube, denoted as A Q(n), is an important variant of the hypercube that possesses several desired topology properties such as diverse embedding schemes in applications of parallel computing. In this paper, we focus on the study of constructing internally disjoint S-trees with vertical bar S vertical bar = 3 in A Q(n). As a result, we completely determine the kappa(3)-connectivity of A Q(n) as follows: kappa(3) (A Q(4)) = 5 and kappa(3) (A Q(n)) = 2n - 2 for n = 3 or n >= 5. (C) 2021 Elsevier Inc. All rights reserved.

Automated summary

This paper focuses on constructing internally disjoint S-trees with |S| = 3 in the n-dimensional augmented cube A Q(n), and completely determines the kappa(3)-connectivity of A Q(n).