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