Back to Search
Start Over
Pendant 3-tree-connectivity of augmented cubes.
- Source :
-
Journal of Supercomputing . Sep2024, Vol. 80 Issue 13, p19395-19413. 19p. - Publication Year :
- 2024
-
Abstract
- 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 . [ABSTRACT FROM AUTHOR]
- Subjects :
- *SPANNING trees
*CUBES
*HYPERCUBES
*TREE graphs
*ELECTRIC circuit networks
Subjects
Details
- Language :
- English
- ISSN :
- 09208542
- Volume :
- 80
- Issue :
- 13
- Database :
- Academic Search Index
- Journal :
- Journal of Supercomputing
- Publication Type :
- Academic Journal
- Accession number :
- 178655195
- Full Text :
- https://doi.org/10.1007/s11227-024-06168-9