# Finding Hamiltonian and Longest \((s,t)\)-Paths of \(C\)-Shaped Supergrid Graphs in Linear Time
## 2 Terminologies and Background Results
Figure 7: **(a–o)** The possible Hamiltonian \((s,t)\)-paths of \(R(3,3)\) when \(s,t\
ot\in\{z_{1},z_{2},z_{3}\}\), and **(p)** the construction of Hamiltonian \((s,t)\)-path of \(R(k+1,3)\) for \(k\geqslant 3\) and \(s,t\in\bar{R}\), where the solid lines indicate the constructed Hamiltonian \((s,t)\)-path and \(\otimes\) represents the destruction of an edge while constructing a Hamiltonian \((s,t)\)-path of \(R(k+1,3)\). in \(C(m,n;k,l;c,d)\) must pass through \(v\) twice. Therefore, \(C(m,n;k,l;c,d)\) contains no Hamiltonian cycle. If part \((\Leftarrow)\): We will prove this statement by constructing a Hamiltonian cycle of \(C(m,n;k,l;c,d)\). There are two cases:  
Case 1: \(c=1\) and \(d=1\). If \(k>1\), then there exists a vertex \(w\in V(C(m,n;k,l;c,d))\) such that \(deg(w)=1\). Thus, \(k=1\). We make vertical and horizontal separations on \(C(m,n;k,l;c,d)\) to obtain three disjoint rectangular supergrid subgraphs \(R_{1}=R(a,n)\), \(R_{2}=R(k,c)\), and \(R_{3}=R(k,d)\), as depicted in Figure 9a. Assume that \(v\in V(R_{2})\) and \(u\in V(R_{3})\). By Lemma 1, \(R_{1}\) contains a canonical Hamiltonian cycle \(HC_{1}\) (see Figure 9b). We can place one flat face of \(HC_{1}\) to face \(R_{2}\) and \(R_{3}\). Thus, there exists an edge \((w,z)\in HC_{1}\) such that \(v\sim w\) and \(v\sim z\). By Statement (3) of Proposition 1, \(v\) and \(HC_{1}\) can be combined into a cycle \(HC_{2}\). By the same argument, \(u\) can be merged into the cycle \(HC_{2}\) to form a Hamiltonian cycle of \(C(m,n;k,l;c,d)\), as shown in Figure 9c. Case 2: \(c\geqslant 2\) or \(d\geqslant 2\). By symmetry, assume that \(d\geqslant 2\). We make a horizontal separation on \(C(m,n;k,l;c,d)\) to obtain two disjoint supergrid subgraphs \(R_{1}=L(m,c+l;k,l)\) and \(R_{2}=R(m,d)\), as depicted in Figure 9d,e, where Figure 9d,e respectively, indicate the case of \(c=1\) and \(c\geqslant 2\). By Theorem 2 (resp. Lemma 1), \(R_{1}\) (resp. \(R_{2}\)) contains a Hamiltonian (resp. canonical Hamiltonian) cycle \(HC_{1}\) (resp. \(HC_{2}\)) such that its one flat face is placed to face \(R_{2}\) (resp. \(R_{1}\)). Then, there exist two edges \(e_{1}=(u_{1},u_{2})\in HC_{1}\) and \(e_{2}=(v_{1},v_{2})\in HC_{2}\) such that \(e_{1}\approx e_{2}\); as shown in Figure 10a,b. By Statement (1) of Proposition 1, \(HC_{1}\) and \(HC_{2}\) can be combined into a Hamiltonian cycle of \(C(m,n;k,l;c,d)\), as shown in Figure 10c,d. Now, we give the necessary and sufficient conditions for the existence of a Hamiltonian \((s,t)\)-path in \(C(m,n;k,l;c,d)\). In addition to condition (F1) (as depicted in Figure 11a,b) and (F3) (as depicted in Figure 11c), if \((C(m,n;k,l;c,d),s,t)\) satisfies one of the following conditions, then it contains no Hamiltonian \((s,t)\)-path. * \(m=3\), \(a(=m-k)=2\), and \([(c=1\) and \(\{s,t\}=\{(1,1),(2,2)\}\) or \(\{(1,2),(2,1)\})\) or \((d=1\) and \(\{s,t\}=\{(1,n),(2,n-1)\}\) or \(\{(1,n-1),(2,n)\})]\) (see Figure 11d). * \(n=3\), \(k=c=d=1\), and  
Figure 10: **(a,b)** Hamiltonian cycles in \(R_{1}\) and \(R_{2}\), and (**c,d**) a Hamiltonian cycle in \(C(m,n;k,l;c,d)\) for Figure 9d,e respectively. Figure 9: **(a)** A vertical and horizontal separation on \(C(m,n;k,l;c,d)\), (b) a Hamiltonian cycle in \(R_{1}\), (c) a Hamiltonian cycle in \(C(m,n;k,l;c,d)\), and (d,e) a horizontal separation on \(C(m,n;k,l;c,d)\), where the bold solid lines indicate the constructed Hamiltonian cycle and \(\otimes\) represents the destruction of an edge while constructing a Hamiltonian cycle. **Lemma 7**. : _If \(HP(C(m,n;k,l;c,d),s,t)\) exists, then \((C(m,n;k,l;c,d),s,t)\) does not satisfy conditions \((\)F1\()\), \((\)F3\()\), \((\)F7\()\), \((\)F8\()\), and \((\)F9\()\)._  
Proof. : Assume that \((C(m,n;k,l;c,d),s,t)\) satisfies one of the conditions (F1), (F3), (F7), (F8), and (F9), then we show that \(HP(C(m,n;k,l;c,d),s,t)\) does not exist. For conditions (F1) and (F3), it is clear (see Figure 11a-c). For condition (F7), by inspecting all cases of Figure 11d there exists no Hamiltonian \((s,t)\)-path.