2021/08/19 by S. A. Mane, Mane, S. A., S. A. Kandekar +1 · 1 citation
Computer Science · Engineering · Mathematics · #16W10(Primary) 06A06 #47L30 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #VLSI and Analog Circuit Testing #VLSI and FPGA Design Techniques #math.CO #msc:06A06 #msc:47L30
paper · pdf · doi:10.48550/arxiv.2108.08865
16 pages, 13 figures
arxiv created 2021/08/19 · openalex publication_date 2021/08/19 · arxiv updated 2021/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Steiner tree problem in graphs has applications in network design or circuit layout. Given a set S of vertices, |S| ≥ 2, a tree connecting all vertices of S is called an S-Steiner tree (tree connecting S). The reliability of a network G to connect any S vertices (|S| number of vertices) in G can be measure by this parameter. For an S-Steiner tree, if the degree of each vertex in S is equal to one, then that tree is called a pendant S-Steiner tree. Two pendant S-Steiner trees T and T' are said to be internally disjoint if E(T) ∩ E(T') = ∅ and V(T) ∩ V(T') = S. The local pendant tree-connectivity τG(S) is the maximum number of internally disjoint pendant S-Steiner trees in G. For an integer k with 2 ≤ k ≤ n, the pendant k-tree-connectivity is defined as τk(G) = min\ τG(S) : S ⊆ V(G), |S| = k\. In this paper, we study the pendant 3-tree connectivity of Augmented cubes which are modifications of hypercubes invented to increase the connectivity and decrease the diameter hence superior to hypercubes. We show that τ3(AQn) = 2n-3. , which attains the upper bound of τ3(G) given by Hager, for G = AQn.