# Directed Path 3-Arc-Connectivity of Cartesian Product Digraphs
## 3 A General Lower Bound
Let  
\(P_{1}:xu_{2,1}yu_{3,2}\), \(P_{2}:xu_{1,2}yu_{2,3}z\), \(P_{3}:xu_{3,1}u_{3,2}yu_{4,2}u_{4,3}z\),  
\(P_{4}:xu_{4,1}u_{4,2}yu_{1,2}u_{1,3}z\), \(P_{5}:xu_{1,3}u_{2,3}yu_{2,4}u_{3,4}z\), \(P_{6}:xu_{1,4}u_{2,4}yu_{2,1}u_{3,1}z\). Furthermore, let \(n=2\), \(m=4\). We can assume that \(x=u_{1,1}\), \(y=u_{1,2}\), \(z=u_{1,3}\). Let  
\(P_{1}:xyz\), \(P_{2}:xyz\), \(P_{3}:xu_{1,4}zu_{2,3}u_{2,2}y\), \(P_{4}:xu_{2,1}u_{2,3}zu_{1,4}y\). Then we have \(n+m-2=\min\left\{\delta^{+}(D),\delta^{-}(D)\right\}\geq\lambda^{p}_{3}( \overleftrightarrow{K}_{n}\square\overleftrightarrow{K}_{m})\geq n+m-2\). This concludes the proof. **Proposition 2**. : _We have \(\lambda_{3}^{p}(\overleftrightarrow{C}_{n}\square\overleftrightarrow{K}_{m})=m+1\), with \(n\geq 3\)._  
Proof. : Let \(S=\{x,y,z\}\), \(r=x\), and we only examine the case where \(x,y\), and \(z\) are not all within the same \(\overleftrightarrow{C}_{n}(u_{i})\) or the same \(\overleftrightarrow{K}_{m}(v_{j})\) for any \(i\in[n],j\in[m]\). The rationale for the remaining cases follows a similar line of argument. Without loss of generality, let us assume \(x=u_{1,1},y=u_{2,2},z=u_{3,3}\). We can obtain \(m+1\) arc-disjoint \((S,r)\)-paths in \(\overleftrightarrow{C}_{n}\square\overleftrightarrow{K}_{m}\), say \(P_{1}\), \(P_{2}\),..., \(P_{i+1}\) (\(4<i\leq m\)), \(P_{m-1}\), \(P_{m}\) (as shown in Figure 9) such that  
\(P_{1}:xu_{2,1}yu_{3,2}\), \(P_{2}:xu_{1,2}yu_{2,3}\), \(P_{3}:xu_{1,n}u_{3,n}u_{3,1}u_{3,2}yu_{1,2}u_{1,3}\),  
\(P_{4}:xu_{3,1}u_{3,n}\),...,\(u_{3,j}...u_{2,3}y\), \(P_{5}:xu_{4,1}u_{4,n}\)... \(u_{4,j}...u_{4,3}zu_{3,2}u_{4,2}y\),  
\(P_{i+1}:xu_{i,1}u_{i,n}\)... \(u_{i,j}...u_{i,3}zu_{i-1,3}u_{i-1,2}u_{i,2}y\). Now, we add two cases to prove that the proposition holds, so as to show that the proposition has no constraint conditions. First, let \(n=3\), \(m=4\). We can assume that \(x=u_{1,1}\), \(y=u_{2,1}\), \(z=u_{3,1}\). Let  
\(P_{1}:xyz\), \(P_{2}:xzy\), \(P_{3}:xu_{4,1}zu_{3,2}u_{2,2}y\), \(P_{4}:xu_{1,3}u_{2,3}yu_{2,2}u_{3,2}u_{3,3}z\). Furthermore, let \(n=3\), \(m=2\). We can assume that \(x=u_{1,1}\), \(y=u_{1,2}\), \(z=u_{1,3}\). Let  
\(P_{1}:xyz\), \(P_{2}:xzu_{2,3}u_{2,2}y\), \(P_{3}:xu_{2,1}u_{2,3}zy\). Then we have \(m+1=\min\{\delta^{+}(D),\delta^{-}(D)\}\geq\lambda_{3}^{p}(\overleftrightarrow {C}_{n}\square\overleftrightarrow{K}_{m})\geq m+1\). This concludes the proof. **Proposition 3**. : _We have \(\lambda_{3}^{p}(\overleftrightarrow{C}_{n}\square\overleftrightarrow{K}_{m})=m\)._Proof. : Let \(S=\{x,y,z\}\), \(r=x\), and we only examine the case where \(x\), \(y\), and \(z\) are not all within the same \(\overrightarrow{C}_{n}(u_{i})\) or the same \(\overleftrightarrow{K}_{m}(v_{j})\) for any \(i\in[n]\), \(j\in[m]\). The rationale for the remaining cases follows a similar line of argument. Without loss of generality, let us assume \(x=u_{1,1}\), \(y=u_{2,2}\), \(z=u_{3,3}\). We can obtain \(m\) arc-disjoint \((S,r)\)-paths in \(\overrightarrow{C}_{n}\square\overleftrightarrow{K}_{m}\). First assume that \(m\) is even number, let  
\(P_{1}:xu_{2,1}yu_{3,2}z\), \(P_{2}:xu_{1,2}yu_{2,3}z\), \(P_{3}:xu_{3,1}u_{3,2}yu_{2,3}z\),  
\(P_{4}:xu_{4,1}u_{4,2}yu_{1,2}u_{1,3}z\), \(P_{1}:xu_{i-1,1}u_{i-1,2}yu_{i,2}u_{i,3}z\),  
\(P_{i}:xu_{i,1}u_{i,2}yu_{i-1,2}u_{i-1,3}z\), \(4<i\leq m\), and \(i\) is an even number. Conversely assume that \(m\) is odd number, let  
\(P_{1}:xu_{2,1}yu_{3,2}z\), \(P_{2}:xu_{1,2}yu_{2,3}z\), \(P_{3}:xu_{3,1}u_{3,2}yu_{1,2}u_{1,3}z\),  
\(P_{i-1}:xu_{i-1,1}u_{i-1,2}yu_{i,2}u_{i,3}z\),  
\(P_{i}:xu_{i,1}u_{i,2}yu_{i-1,2}u_{i-1,3}z\), \(3<i\leq m\), and \(i\) is an odd number. Then we have \(m=\min\{\delta^{+}(D),\delta^{-}(D)\}\geq\lambda_{3}^{p}(\overrightarrow{C}_{ n}\square\overleftrightarrow{K}_{m})\geq m\). This completes the proof. Proposition 4.: _We have \(\lambda_{3}^{p}(\overleftrightarrow{T}_{n}\square\overleftrightarrow{K}_{m})=m\)._  
Proof.