Constructing Internally Disjoint Pendant Steiner Trees in Cartesian Product Networks

The concept of pedant tree-connectivity was introduced by Hager in 1985. For a graph $G=(V,E)$ and a set $S\subseteq V(G)$ of at least two vertices, \emph{an $S$-Steiner tree} or \emph{a Steiner tree connecting $S$} (or simply, \emph{an $S$-tree}) is a such subgraph $T=(V^{\mathrm{\prime }},E^{\mathrm{\prime }})$ of $G$ that is a tree with $S\subseteq V^{\mathrm{\prime }}$. For an $S$-Steiner tree, if the degree of each vertex in $S$ is equal to one, then this tree is called a \emph{pedant $S$-Steiner tree}. Two pedant $S$-Steiner trees $T$ and $T^{\mathrm{\prime }}$ are said to be \emph{internally disjoint} if $E(T)\cap E(T^{\mathrm{\prime }})=\mathrm{\varnothing }$ and $V(T)\cap V(T^{\mathrm{\prime }})=S$. For $S\subseteq V(G)$ and $\mathrm{\mid }S\mathrm{\mid }\ge 2$, the \emph{local pedant tree-connectivity} ${\tau }_G(S)$ is the maximum number of internally disjoint pedant $S$-Steiner trees in $G$. For an integer $k$ with $2\le k\le n$, \emph{pedant tree $k$-connectivity} is defined as ${\tau }_k(G)=\min \{{\tau }_G(S)\mathrm{\mid }S\subseteq V(G),\mathrm{\mid }S\mathrm{\mid }=k\}$. In this paper, we prove that for any two connected graphs $G$ and $H$, $\tau_3(G\Box H)\geq \min{3\lfloor\frac{\tau_3(G)}{2}\rfloor,3\lfloor\frac{\tau_3(H)}{2}\rfloor}$. Moreover, the bound is sharp.