Packing internally disjoint Steiner paths of data center networks

Abstract

Let $S\subseteq V(G)$ and ${\pi }_G(S)$ denote the maximum number $t$ of edge-disjoint paths $P_1,P_2,\dots ,P_t$ in a graph $G$ such that $V(P_i)\cap V(P_j)=S$ for any $i,j\in \{1,2,\dots ,t\}$ and $i\ne j$. If $S=V(G)$, then ${\pi }_G(S)$ is the maximum number of edge-disjoint spanning paths in $G$. It is proved [Graphs Combin., 37 (2021) 2521-2533] that deciding whether ${\pi }_G(S)\ge r$ is NP-complete for a given $S\subseteq V(G)$. For an integer $r$ with $2\le r\le n$, the $r$-path connectivity of a graph $G$ is defined as ${\pi }_r(G)=$min$\{{\pi }_G(S)|S\subseteq V(G)$ and $|S|=r\}$, which is a generalization of tree connectivity. In this paper, we study the $3$-path connectivity of the $k$-dimensional data center network with $n$-port switches $D_{k,n}$ which has significate role in the cloud computing, and prove that ${\pi }_3(D_{k,n})=\lfloor \frac{2n+3k}{4}\rfloor$ with $k\ge 1$ and $n\ge 6$.