# Finding Hamiltonian and Longest \((s,t)\)-Paths of \(C\)-Shaped Supergrid Graphs in Linear Time
## 2 Terminologies and Background Results
If \((R(m,n),s,t)\) does not satisfy condition (F1), then there exists a canonical Hamiltonian \((s,t)\)-path \(P\) of \(R(m,n)\) such that \((z,f)\in P\) if \((R(m,n),s,t)\) does satisfy condition (F2); and \((w,z)\in P\) otherwise, where condition (F2) is defined as follows:_  
* \(n=2\) and \(\{s,t\}\in\{\{w,z\},\{(1,1),(2,2)\},\{(2,1),(1,2)\}\}\), or \(n\geqslant 3\) and \(\{s,t\}=\{w,z\}\). We then give some observations on the relations among cycle, path, and vertex. These propositions will be used in proving our results and are given in [12]. **Proposition 1** (See [12]). : _Let \(G\) be a graph. Assume \(C_{1}\) and \(C_{2}\) are two vertex-disjoint cycles of \(G\), \(P_{1}\) and \(P_{2}\) are two vertex-disjoint paths of \(G\), \(C_{1}\) and \(P_{1}\) are a cycle and a path, respectively, of \(G\) with \(V(C_{1})\cap V(P_{1})=\emptyset\), and assume \(x\) is a vertex in \(G-V(C_{1})\) or \(G-V(P_{1})\). Then, the following statements hold true:_  
Figure 4: A canonical Hamiltonian cycle containing three flat faces and one concave face for (**a**) \(R(6,6)\), and (**b**–**e**) \(R(5,5)\), where the solid arrow lines indicate the edges in the cycles and \(R(5,5)\) contains four distinct canonical Hamiltonian cycles in (**b**–**e**) such that their concave faces are placed on different boundaries. Figure 5: Rectangular supergrid graphs in which there is no Hamiltonian \((s,t)\)-path for (**a**) \(R(m,1)\), and (**b**) \(R(m,2)\), where solid lines indicate the longest path between \(s\) and \(t\). \((1)\) _If there exist two edges_ \(e_{1}\in C_{1}\) _and_ \(e_{2}\in C_{2}\) _such that_ \(e_{1}\approx e_{2}\)_, then_ \(C_{1}\) _and_ \(C_{2}\) _can be combined into a cycle of_ \(G\) _(see Figure_ 6_a)._ \((2)\) _If there exist two edges_ \(e_{1}\in C_{1}\) _and_ \(e_{2}\in P_{1}\) _such that_ \(e_{1}\approx e_{2}\)_, then_ \(C_{1}\) _and_ \(P_{1}\) _can be combined into a path of_ \(G\) _(see Figure_ 6_b)._ \((3)\) _If vertex_ \(x\) _adjoins one edge_ \((u_{1},v_{1})\) _of_ \(C_{1}\) _(resp.,_ \(P_{1}\)_), then_ \(C_{1}\) _(resp.,_ \(P_{1}\)_) and_ \(x\) _can be merged into a cycle (resp., path) of_ \(G\) _(see Figure_ 6_c)._ \((4)\) _If there exists one edge_ \((u_{1},v_{1})\in P_{1}\) _such that_ \(u_{1}\sim start(P_{2})\) _and_ \(v_{1}\sim end(P_{2})\)_, then_ \(P_{1}\) _and_ \(P_{2}\) _can be combined into a path of_ \(G\) _(see Figure_ 6_d)._  
Next, we will discover one Hamiltonian connected property of \(3\)-rectangle \(R(m,3)\) with \(m\geqslant 3\) that will be used in to prove our result. Let \(z_{1}=(m,1)\), \(z_{2}=(m,2)\), and \(z_{3}=(m,3)\) be three vertices of \(R(m,3)\). Assume that \(\tilde{R}=R(m,3)-\{z_{1},z_{2},z_{3}\}\) and edges \(e_{12}=(z_{1},z_{2})\), \(e_{23}=(z_{2},z_{3})\). Assume that \(s,t\in\tilde{R}\). We will prove that there exists a Hamiltonian \((s,t)\)-path \(P\) of \(R(m,3)\) such that \(e_{12},e_{23}\in P\). Before giving this property, we first give one result in [12] for \(3\)-rectangle as follows. **Lemma 5** (See [12]). : _Assume \(R(m,3)\) is a \(3\)-rectangle with \(m\geqslant 3\) and \(s,t\) being its two distinct vertices. Then, \(R(m,3)\) contains a canonical Hamiltonian \((s,t)\)-path which contains at least one boundary edge of each boundary in \(R(m,3)\)._  
By using the above lemma, we will prove the following lemma. **Lemma 6**. : _Assume \(R(m,3)\) is a \(3\)-rectangle with \(m\geqslant 3\) and \(s,t\) being its two distinct vertices. Let \(z_{1}=(m,1)\), \(z_{2}=(m,2)\), and \(z_{3}=(m,3)\), which are the three vertices of \(R(m,3)\), and let edges \(e_{12}=(z_{1},z_{2})\), \(e_{23}=(z_{2},z_{3})\). If \(\{s,t\}\cap\{z_{1},z_{2},z_{3}\}=\emptyset\), then there exists a Hamiltonian \((s,t)\)-path of \(R(m,3)\) containing \(e_{12}\) and \(e_{23}\)._  
Proof. : We will prove this lemma by induction on \(m\). Let \(\tilde{R}=R(m,3)-\{z_{1},z_{2},z_{3}\}\). Then, \(\tilde{R}=R(m-1,3)\), where \(m-1\geqslant 2\). Initially, let \(m=3\). Then, \(\tilde{R}=R(2,3)\) and \(s,t\in\tilde{R}\).