Institute of Mathematics

Abstract:  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 internally disjoint if they share no vertices other than $S$ and have no edges in common. For $S\subseteq V(G)$ and $|S|\geq2$, the pendant tree-connectivity $\tau_G(S)$ is the maximum number of internally disjoint pendant $S$-Steiner trees in $G$, and for $k \geq2$, 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.