Completely independent Steiner trees and corresponding tree connectivity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915692268224512 |
|---|---|
| author | Yuan, Jun Liu, Shan Lin, Shangwei Liu, Aixia |
| author_facet | Yuan, Jun Liu, Shan Lin, Shangwei Liu, Aixia |
| contents | The $S$-Steiner tree packing problem provides mathematical foundations for optimizing multi-path information transmission, particularly in designing fault-tolerant parallelized routing architectures for massive-scale network infrastructures. In this article, we propose the definitions of completely independent $S$-Steiner trees (CISSTs for short) and generalized $k^*$-connectivity, which generalize the definitions of internally disjoint $S$-Steiner trees and generalized $k$-connectivity. Given a connected graph $G = (V,E)$ and a vertex subset $S\subseteq V, |S|\geq 2,$ an $S$-Steiner tree of $G$ is a subtree in $G$ that spans all nodes in $S.$ The $S$-Steiner trees $T_1,T_2,\cdots, T_k$ of $G$ are completely independent pairwise if for any $1\leq p<q\leq k,$ $E(T_p)\cap E(T_q)=\emptyset$ , $V(T_p)\cap V(T_q)=S,$ and for any two vertices $x_{1},x_{2}$ in $S$, the paths connecting $x_{1}$ and $x_{2}$ in $T_p,T_q$ are pairwise internally disjoint. The packing number of CISSTs, denoted by $κ^*_G(S),$ is the maximum number of CISSTs in $G.$ The generalized $k^*$-connectivity $κ_k^*(G)$ is the minimum $κ_G^*(S)$ for $S$ ranges over all $k$-subsets of $V(G).$ We provide a detailed characterization of CISSTs. Also, we investigate the CISSTs of complete graphs and complete bipartite graphs. Furthermore, we determine the generalized $k^*$-connectivity for complete graphs and give a tight lower bound of the generalized $k^*$-connectivity for complete bipartite graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_19973 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Completely independent Steiner trees and corresponding tree connectivity Yuan, Jun Liu, Shan Lin, Shangwei Liu, Aixia Combinatorics The $S$-Steiner tree packing problem provides mathematical foundations for optimizing multi-path information transmission, particularly in designing fault-tolerant parallelized routing architectures for massive-scale network infrastructures. In this article, we propose the definitions of completely independent $S$-Steiner trees (CISSTs for short) and generalized $k^*$-connectivity, which generalize the definitions of internally disjoint $S$-Steiner trees and generalized $k$-connectivity. Given a connected graph $G = (V,E)$ and a vertex subset $S\subseteq V, |S|\geq 2,$ an $S$-Steiner tree of $G$ is a subtree in $G$ that spans all nodes in $S.$ The $S$-Steiner trees $T_1,T_2,\cdots, T_k$ of $G$ are completely independent pairwise if for any $1\leq p<q\leq k,$ $E(T_p)\cap E(T_q)=\emptyset$ , $V(T_p)\cap V(T_q)=S,$ and for any two vertices $x_{1},x_{2}$ in $S$, the paths connecting $x_{1}$ and $x_{2}$ in $T_p,T_q$ are pairwise internally disjoint. The packing number of CISSTs, denoted by $κ^*_G(S),$ is the maximum number of CISSTs in $G.$ The generalized $k^*$-connectivity $κ_k^*(G)$ is the minimum $κ_G^*(S)$ for $S$ ranges over all $k$-subsets of $V(G).$ We provide a detailed characterization of CISSTs. Also, we investigate the CISSTs of complete graphs and complete bipartite graphs. Furthermore, we determine the generalized $k^*$-connectivity for complete graphs and give a tight lower bound of the generalized $k^*$-connectivity for complete bipartite graphs. |
| title | Completely independent Steiner trees and corresponding tree connectivity |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.19973 |