Pendant 3-tree-connectivity of augmented cubes

• Published in: The Journal of supercomputing 2024-09, Vol.80 (13), p.19395-19413
• Main Authors: Mane, S. A., Kandekar, S. A.
• Format: Article
• Language: English
• Subjects: Apexes; Compilers; Computer Science; Connectivity; Cubes; Graph theory; Hypercubes; Interpreters; Network design; Processor Architectures; Programming Languages; Trees (mathematics); Upper bounds
• ISSN: 0920-8542; 1573-0484
• DOI: 10.1007/s11227-024-06168-9

The Steiner tree problem in graphs is widely studied because of its usefulness in network design and circuit layout. In this context, given a set of vertices S ( | S | ≥ 2 , ) a tree that connects all vertices in S is called an S -Steiner tree. This helps to measure how well a network G can connect any set of S vertices together. In an S -Steiner tree, if each vertex in S has only one connection, it is called a pendant S -Steiner tree. Two pendant S -Steiner trees, T and T ′ , are internally disjoint if E ( T ) ∩ E ( T ′ ) = ∅ and V ( T ) ∩ V ( T ′ ) = S . The local pendant tree-connectivity, denoted as τ G ( S ) , represents the maximum number of internally disjoint pendant S -Steiner trees in graph G . For an integer k with 2 ≤ k ≤ n , where n is the number of vertices, the pendant k -tree-connectivity, denoted as τ k ( G ) , is defined as τ k ( G ) = m i n { τ G ( S ) : S ⊆ V ( G ) , | S | = k } . This paper focuses on studying the pendant 3-tree-connectivity of augmented cubes, which are modified versions of hypercubes designed to enhance connectivity and reduce diameter. This research demonstrates that the pendant 3-tree-connectivity of augmented cubes, denoted as τ 3 ( A Q n ) is 2 n - 3 . This result matches the upper bound of τ 3 ( G ) provided by Hager, specifically for the augmented cube graph A Q n .