A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs

Mao, Yaping ; Melekian, Christopher ; Cheng, Eddie

Czechoslovak Mathematical Journal, Tome 73 (2023) no. 1, pp. 237-244.

Résumé

For a connected graph $G=(V,E)$ and a set $S \subseteq V(G)$ with at least two vertices, an $S$-Steiner tree is a subgraph $T = (V',E')$ of $G$ that is a tree with $S \subseteq V'$. If the degree of each vertex of $S$ in $T$ is equal to 1, then $T$ is called a pendant $S$-Steiner tree. Two $S$-Steiner trees are {\it internally disjoint} if they share no vertices other than $S$ and have no edges in common. For $S\subseteq V(G)$ and $|S|\geq 2$, the pendant tree-connectivity $\tau _G(S)$ is the maximum number of internally disjoint pendant $S$-Steiner trees in $G$, and for $k \geq 2$, the $k$-pendant tree-connectivity $\tau _k(G)$ is the minimum value of $\tau _G(S)$ over all sets $S$ of $k$ vertices. We derive a lower bound for $\tau _3(G\circ H)$, where $G$ and $H$ are connected graphs and $\circ $ denotes the lexicographic product.

Détail

DOI : 10.21136/CMJ.2022.0057-22

Classification : 05C05, 05C40, 05C70, 05C76
Keywords: connectivity; Steiner tree; internally disjoint Steiner tree; packing; pendant tree-connectivity, lexicographic product