# Directed Path 3-Arc-Connectivity of Cartesian Product Digraphs
## 3 A General Lower Bound
In \(H(u_{2})\), with \(S^{\prime}_{3}=\{y,u_{2,3}\}\), \(r^{\prime}_{3}=y\), it is known that there exist at least \(\kappa(G)\) internally disjoint \((S^{\prime}_{3},r^{\prime}_{3})\)-paths, denoted as \(\overline{P}_{2j}\). For each \(j\in[\kappa(G)]\), let \(u_{2,f_{j}}\) be the out-neighbor of \(y\) in \(\overline{P}_{2j}\), clearly these out-neighbors are distinct. In \(G(v_{2})\), with \(S_{3}=\{y,u_{3,2}\}\), \(r_{3}=y\), it is known that there exist at least \(\kappa(G)\) internally disjoint \((S_{3},r_{3})\)-paths in \(G(v_{2})\), denoted as \(\overline{P}_{1i}\). For each \(i\in[\kappa(G)]\), let \(u_{i,j,2}\) be the out-neighbor of \(y\) in \(\overline{P}_{1i}\), clearly these out-neighbors are distinct. For each \(i\in[\kappa(G)]\), an out-neighbor of \(u_{i,j,2}\) in \(H(u_{i_{j}})\) can be chosen, denoted by \(u_{i,j,\kappa}\) (\(c\in[m]\)), with \(c\
otin\{1,3\}\). In \(G(v_{c})\), with \(S_{4}=\{u_{2,c},u_{3,c}\}\), \(r_{4}=u_{2,c}\). \(\overline{P}^{\prime}_{1i}\) is the \((S_{4},r_{4})\)-path corresponding to \(\overline{P}_{1i}\). In \(\overline{P}^{\prime}_{1i}\), the path from vertex \(u_{i_{j},c}\) to \(u_{3,c}\) is denoted as \(\overline{P}^{\prime\prime}_{1i}\). In \(H(u_{3})\), with \(S_{5}=\{u_{3,c},z\}\), \(r_{5}=u_{3,c}\), and it is known that there exist at least \(\kappa(G)\) internally disjoint \((S_{5},r_{5})\)-paths, say \(\bar{P}_{1i}\). In \(H(v_{b})\), with \(S^{\prime}_{4}=\{u_{b,2},u_{b,3}\}\), \(r^{\prime}_{4}=u_{b,2}\), \(\overline{P}^{\prime}_{2j}\) is the \((S^{\prime}_{4},r^{\prime}_{4})\)-path corresponding to \(\overline{P}_{2j}\). In path \(\overline{P}^{\prime}_{2j}\), the path from vertex \(u_{b,f_{j}}\) to \(u_{b,3}\) is denoted as \(\overline{P}^{\prime}_{2j}\). In \(G(v_{3})\), with \(S^{\prime}_{5}=\{u_{b,3},z\}\), \(r^{\prime}_{5}=u_{b,3}\), and it is known that there exist at least \(\kappa(G)\) internally disjoint \((S^{\prime}_{5},r^{\prime}_{5})\)-paths in \(G(v_{3})\), say \(\bar{P}_{2j}\). If \(u_{i_{5},2}=u_{3,2}\), then \(u_{3,2}\
otin\bar{P}_{1k}\) (\(k\in[\kappa(G)]\)). If \(u_{3,1}\in\widetilde{P}_{1t}\), then \(u_{3,1}\
otin\bar{P}_{1t}\) (\(t\in[\kappa(G)]\)). Similarly, if \(u_{2,f_{j}}=u_{2,3}\), then \(u_{2,3}\
otin\bar{P}_{2r}\) (\(r\in[\kappa(G)]\)). If \(u_{1,3}\in\widehat{P}_{2h}\), then \(u_{1,3}\
otin\bar{P}_{2h}\) (\(h\in[\kappa(G)]\)). The arc-disjoint \((S,r)\)-paths can be constructed as \(P_{1i}=\widehat{P}_{1i}\cup\widehat{P}_{1i}\cup\overline{P}^{\prime\prime}_{1 i}\cup\bar{P}_{1i}\cup\{yu_{i_{5},2},u_{i_{5},2}u_{i_{5},c}\}\), \(P_{2j}=\widehat{P}_{2j}\cup\widehat{P}_{2j}\cup\overline{P}^{\prime\prime}_{2 j}\cup\{yu_{2,f_{j}},u_{2,f_{j}}u_{b,f_{j}}\}\). Then we obtain \(2\kappa(G)\) arc-disjoint \((S,r)\)-paths. **Case 4. **: Let \(x\) and \(y\) be in the same \(H(u_{i})\). Let \(z\), \(x\), and \(y\) be in different \(G(v_{j})\) and let \(z\), \(x\) be in different \(H(u_{i})\), for some \(i\in[n]\), \(j\in[m]\). Without loss of generality, we can assume  
Figure 2.2 Depiction of the arc-disjoint paths found in Case 3 of the proof of Theorem 1.  
that \(x=u_{2,1}\), \(y=u_{2,2}\), \(z=u_{3,3}\). In this case, our overall goal is that we will use arc-disjoint paths between \(x\) and \(y\) in \(H(u_{2})\), \(y\) and its out-neighbors in \(G(v_{2})\), \(z\) and its in-neighbors in \(H(u_{3})\), \(x\) and its out-neighbors in \(G(v_{2})\), \(y\) and its out-neighbors in \(H(u_{2})\), \(z\) and its in-neighbors in \(G(v_{3})\), and combine them together to form the required arc-disjoint paths. The general idea of the proof process is briefly described in Figure 2.3 The vertices and paths contained in Figure 5 are explained below. Considering \(S_{1}=\{x,y\}\), \(r_{1}=x\), it is known that there exist at least \(\kappa(G)\) internally disjoint \((S_{1},r_{1})\)-paths in \(H(u_{2})\), denoted as \(\widetilde{P}_{1i}\)\((i\in[\kappa(G)])\).