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

• The generalized k -connectivity κ k (G) is the maximum number of internally disjoint trees connecting any k vertices of G. • The substructure properties of the n -dimensional augmented cube A Q n are given. • The results of κ 3 (A Q n) = 2 n − 2 for n = 3 or n ≥ 5 are derived. • κ 3 (A Q 4) = 5 is derived. Given a connected graph G and S ⊆ V (G) with | S | ≥ 2 , a tree T in G is called an S -Steiner tree (or S -tree for short) if S ⊆ V (T). Two S -trees T 1 and T 2 are internally disjoint if E (T 1) ∩ E (T 2) = ∅ and V (T 1) ∩ V (T 2) = S. The packing number of internally disjoint S -trees, denoted as κ G (S) , is the maximum size of a set of internally disjoint S -trees in G. For an integer k ≥ 2 , the generalized k -connectivity (abbr. κ k -connectivity) of a graph G is defined as κ k (G) = min { κ G (S) | S ⊆ V (G) and | S | = k }. 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 | S | = 3 in A Q n. As a result, we completely determine the κ 3 -connectivity of A Q n as follows: κ 3 (A Q 4) = 5 and κ 3 (A Q n) = 2 n − 2 for n = 3 or n ≥ 5. [ABSTRACT FROM AUTHOR]