# Directed Path 3-Arc-Connectivity of Cartesian Product Digraphs
## 1 Introduction  
For a detailed explanation of graph theoretical notation and terminology not provided here, readers are directed to reference [1]. It should be noted that all digraphs discussed in this paper do not contain parallel arcs or loops. The set of all natural numbers from \(1\) to \(n\) is denoted by \([n]\). If a directed graph \(D\) can be obtained from its underlying graph \(G\) by replacing each edge in \(G\) with corresponding arcs in both directions, then \(D\) is said to be symmetric, denoted as \(D=\overleftarrow{G}\). The notation \(\overleftarrow{T}_{n}\) is used for a symmetric digraph whose underlying graph forms a tree of order \(n\). The notation \(\overleftarrow{\mathcal{C}}_{n}\) is used for a symmetric digraph whose underlying graph forms a cycle of order \(n\). The cycle digraph of order \(n\) is denoted by \(\overleftarrow{C}_{n}\). We denote the complete digraph of order \(n\) as \(\overleftarrow{\mathcal{C}}_{n}\). The well-known Steiner tree packing problem is characterized as follows. Given a graph \(G\) and a set of terminal vertices \(S\subseteq V(G)\), the goal is to identify as many edge-disjoint S-Steiner trees (i.e., trees \(T\) in \(G\) with \(S\subseteq V(T)\)) as feasible. This particular problem, along with its associated topics, garners significant interest from researchers due to its extensive applications in VLSI circuit design [2; 3; 4] and Internet Domain [5]. In practical applications, the construction of vertex-disjoint or arc-disjoint paths in graphs holds significance, as they play a crucial role in improving transmission reliability and boosting network transmission rates [6]. This paper will specifically delve into a variant of the directed Steiner tree packing problem, termed the directed Steiner path packing problem, closely interconnected with the Steiner path problem and the Steiner path cover problem [7; 8]. We now consider two types of directed Steiner path packing problems and related parameters. Let \(D=(V(D),A(D))\) be a digraph of order \(n\) and let \(r\in S\subseteq V(D)\) with \(2\leq|S|\leq n\). A directed \((S,r)\)-Steiner path, or simply an \((S,r)\)-path, refers to a directed path \(P\) originating from \(r\) such that \(S\) is a subset of the vertices in \(P\). Arc-disjoint between two \((S,r)\)-paths implies that they share no common arcs, while two arc-disjoint \((S,r)\)-paths are internally disjoint when their common vertex set is precisely \(S\). Let \(\lambda_{S,r}^{P}(D)\) (and \(\kappa_{S,r}^{p}(D)\)) represent the maximum number of arc-disjoint (and internally disjoint) \((S,r)\)-paths in \(D\), respectively. The Arc-disjoint (or Internally disjoint) Directed Steiner Path Packing problem is formulated as follows. Given a digraph \(D\) and letting \(r\in S\subseteq V(D)\), the objective isto maximize the count of arc-disjoint (or internally disjoint) \((S,r)\)-paths. The notion of directed path connectivity, which is a derivative of path connectivity in undirected graphs, is intricately linked to the directed Steiner path packing problem and serves as a logical progression from path connectivity in directed graphs (refer to [5] for the initial presentation of path connectivity). The directed path \(k\)-connectivity [9] of \(D\) is defined as  
\[\kappa_{k}^{p}(D)=\min\{\kappa_{S,r}^{p}(D)\mid S\subseteq V(D),|S|=k,r\in S\}\]  
Similarly, the directed path \(k\)-arc-connectivity [9] of \(D\) is defined as  
\[\lambda_{k}^{p}(D)=\min\{\lambda_{S,r}^{p}(D)\mid S\subseteq V(D),|S|=k,r\in S\}\]  
The concepts of directed path \(k\)-connectivity and directed path \(k\)-arc-connectivity are synonymous with directed path connectivity. In the context of \(k=2\), \(\kappa_{2}^{p}(D)\) equates to \(\kappa(D)\) and \(\lambda_{2}^{p}(D)\) equates to \(\lambda(D)\), where \(\kappa(D)\) and \(\lambda(D)\) denote vertex-strong connectivity and arc-strong connectivity of digraphs, respectively. Hence, these parameters can be viewed as extensions of the classical connectivity measures in a digraph.