Internally-disjoint directed pendant Steiner trees with three terminal vertices in Cartesian product digraphs

Abstract

Let $D=(V(D),A(D))$ be a digraph with a terminal vertex subset $S\subseteq V(D)$ such that $|S|=k\ge 2$. An out-tree $T$ of $D$ rooted at $r$ is called a directed pendant $(S,r)$-Steiner tree (or, pendant $(S,r)$-tree for short) if $r\in S\subseteq V(T)$ and $d_T^{+}(r)=d_T^{-}(u)=1$ for each $u\in S\backslash \{r\}$. Two pendant $(S,r)$-trees $T_1$ and $T_2$ are internally-disjoint if $A(T_1)\cap A(T_2)=\varnothing$ and $V(T_1)\cap V(T_2)=S$. The pendant-tree $k$-connectivity $\ddot{I}{„}_k(D)$ of $D$ is defined as $$\ddot{I}{„}_k(D)=\min \{\ddot{I}{„}_{S,r}(D)\mid S\subseteq V(D),|S|=k,r\in S\},$$ where $\ddot{I}{„}_{S,r}(D)$ denotes the maximum number of pairwise internally-disjoint pendant $(S,r)$-trees in $D$. In this paper, we derive a sharp lower bound for the pendant-tree 3-connectivity of the Cartesian product digraph $D\square H$, where $D$ and $H$ are both strong digraphs. Specifically, we prove the lower bound $\ddot{I}{„}_3(D\square H)\ge \ddot{I}{„}_3(D)+\ddot{I}{„}_3(H)$. Moreover, we propose a polynomial-time algorithm for finding internally-disjoint pendant $(S,r)$-trees which attain this lower bound.