# Directed Path 3-Arc-Connectivity of Cartesian Product Digraphs
## 3 A General Lower Bound
If there is no such vertex, then let \(b\
eq k_{j}\). In \(H(u_{b})\), \(\widetilde{P}^{\prime}_{1i}\) is the \((S_{3},r_{3})\)-path corresponding to \(\widetilde{P}_{1i}\), where \(S_{3}=\{u_{b,1},u_{b,d}\}\), and \(r_{3}=u_{b,1}\). In \(\overline{P}^{\prime}_{1i}\), the path from vertex \(u_{b,f_{i}}\) to \(u_{b,d}\) is denoted as \(\overline{P}^{\prime\prime}_{1i}\). Let \(S_{4}=\{u_{b,d},u_{3,d}\}\), \(r_{4}=u_{b,d}\), and it is established that there exist at least \(\kappa(G)\) internally disjoint \((S_{4},r_{4})\)-paths, say \(\widetilde{P}_{1i}\)\((i\in[\kappa(G)])\). If \(u_{2,f_{i}}=u_{2,d}\)\((t\in[\kappa(G)])\), then let \(u_{2,d}\
otin\widehat{P}_{1i}\) in \(\widehat{P}_{1i}\). In \(H(u_{3})\), let \(S_{5}=\{u_{3,d},z\}\), \(r_{5}=u_{3,d}\), and it is established that there exist at least \(\kappa(G)\) internally disjoint \((S_{5},r_{5})\)-paths, say \(\widetilde{P}_{1i}\)\((i\in[\kappa(G)])\). In \(H(u_{1})\), if there is an out-neighbor of \(x\) that is not an out-neighbor of \(x\) in \(\widetilde{P}_{2j}\), then choose such a vertex as \(u_{1,c}\), with \(c\
otin\{a,d\}\). If there is no such vertex, then choose any out-neighbor of \(x\) as \(u_{1,c}\), with \(c\
otin\{a,d\}\). And \(u_{s_{j},c}\) is an out-neighbor of \(u_{s_{j},1}\) in \(H(u_{s_{j}})\). In \(G(v_{c})\), \(\overline{P}^{\prime}_{2j}\) is the \((S^{\prime}_{5},r^{\prime}_{5})\)-path corresponding to \(\widetilde{P}_{2j}\), where \(S^{\prime}_{5}=\{u_{2,c},u_{3,c}\}\) and \(r^{\prime}_{5}=u_{2,c}\). In \(\overline{P}^{\prime}_{2j}\), the path from vertex \(u_{s_{j},c}\) to \(u_{k_{j},c}\) is denoted as \(\overline{P}^{\prime\prime}_{2j}\). If \(u_{s_{s},1}=u_{k_{j},1}\)\((t\in[\kappa(G)])\), then \(\overline{P}^{\prime\prime}_{2t}=\{yu_{s_{j},1},u_{s_{j},1}z\}\). If \(u_{s_{j},1}=z\)\((l\in[\kappa(G)])\), then \(\overline{P}^{\prime\prime}_{2l}=\{yz\}\). If \(u_{1,c}\in\overline{P}^{\prime\prime}_{2h}\)\((h\in[\kappa(G)])\), then \(u_{1,c}\
otin\widetilde{P}_{2h}\). In \(H(u_{k_{j}})\), with \(S^{\prime}_{6}=\{u_{k_{j},c},u_{k_{j},1}\}\), and \(r^{\prime}_{6}=u_{k_{j},c}\), it is known that there  
Figure 2: Depiction of the arc-disjoint paths found in Case 1 of the proof of Theorem 1.  
exist at least \(\kappa(G)\) internally disjoint \((S^{\prime}_{6},r^{\prime}_{6})\)-paths. Then in these paths, one of the paths \(\widetilde{P}_{2j}\)\((j\in[\kappa(G)])\) is chosen, with \(u_{k_{j},a}\
otin\widetilde{P}_{2j}\). **Subcase 1.1. **: In the set \(\{u_{s_{j},1},u_{k_{j},1}\}\), there is no vertex such that \(u_{s_{j},1}=x\) or \(u_{k_{j},1}=x\), and the vertex \(z\) is not in path \(\widetilde{P}_{1i}\). We now construct the arc-disjoint \((S,r)\)-paths by letting  
\[P_{1i} =\widetilde{P}_{1i}\cup\widetilde{P}_{1i}^{\prime\prime}\cup \widehat{P}_{1i}\cup\widetilde{P}_{1i}\cup\{yu_{2,f_{i}}u_{2,f_{i}}u_{b,f_{i} }\},i\in[\kappa(G)],\] \[P_{2j} =\widetilde{P}_{2j}\cup\widehat{P}_{2j}\cup\widetilde{P}_{2j}\cup \overline{P}_{2j}^{\prime\prime}\cup\widetilde{P}_{2j}\cup\{yu_{s_{j},1}u_{s_{ j},1}u_{s_{j},c},u_{k_{j},1}z\},j\in[\kappa(G)]\setminus\{t,l\},\] \[P_{2t} =\widetilde{P}_{2t}\cup\widehat{P}_{2t}\cup\overline{P}_{2t}^{ \prime\prime}\cup\widetilde{P}_{2t},\] \[P_{2t} =\widetilde{P}_{2t}\cup\widehat{P}_{2t}\cup\overline{P}_{2t}^{ \prime\prime}\cup\widetilde{P}_{2t}.\] Then we obtain \(2\kappa(G)\) arc-disjoint \((S,r)\)-paths. **Subcase 1.2. **: In the set \(\{u_{s_{j},1},u_{k_{j},1}\}\), there is no vertex such that \(u_{s_{j},1}=x\) or \(u_{k_{j},1}=x\), and there exist \(z\in\widetilde{P}_{1h}\)\((h\in[\kappa(G)])\), but there is no arc \(u_{k_{j},1}z\) in path \(\widetilde{P}_{1h}\). Let \(P_{1h}=\widetilde{P}_{1h}\). The other paths are the same as Subcase 1.1. **Subcase 1.3. **: There is an arc \(u_{k_{r},1}z\) in path \(\widetilde{P}_{1h}\)\((\{r,h\}\subseteq[\kappa(G)])\). In the set \(\{u_{s_{j},1},u_{k_{j},1}\}(j\
eq r)\), there is no vertex \(x\). We can find a path \(\widetilde{P}_{2r}\) such that \(u_{2,f_{h}}\
otin\widetilde{P}_{2r}\).