# Finding Hamiltonian and Longest \((s,t)\)-Paths of \(C\)-Shaped Supergrid Graphs in Linear Time
## 2 Terminologies and Background Results
By considering every case, we can construct the desired Hamiltonian \((s,t)\)-path of \(R(3,3)\), as shown in Figure 7a-o. Assume that the lemma holds true when \(m=k\geqslant 3\). Consider that \(m=k+1\). Then, \(\tilde{R}=R(k,3)\) is a subgraph of \(R(k+1,3)\), where \(z_{1}=(k+1,1)\), \(z_{2}=(k+1,2)\), \(z_{3}=(k+1,3)\), and \(s,t\in\tilde{R}=R(k,3)\). Let \(\tilde{P}=z_{1}\to z_{2}\to z_{3}\). By Lemma 5, \(\tilde{R}\) contains a Hamiltonian \((s,t)\)-path \(\tilde{P}\) such that it contains an edge \(\tilde{e}=(u,v)\) locating to face \(R(k+1,3)-\tilde{R}\). Then, \(start(\tilde{P})\thicksim u\) and \(end(\tilde{P})\thicksim v\). By Statement (4) of Proposition 1, \(\tilde{P}\) and \(\tilde{P}\) can be combined into a Hamiltonian \((s,t)\)-path of \(R(k+1,3)\). The construction of such a Hamiltonian path is depicted in Figure 7p. Thus, the lemma holds when \(m=k+1\). By induction, the lemma holds true. In addition to condition (F1) (see Figure 8a,b), in [17], we showed that \(HP(L(m,n;k,l),s,t)\) does not exist whenever one of the following conditions is satisfied. * assume that \(G\) is a supergrid graph, there exists a vertex \(w\in G\) such that \(deg(w)=1\), \(w\
eq s\), and \(w\
eq t\) (see Figure 8c). * \(m-k=1\), \(n-l=2\), \(l=1\), \(k\geqslant 2\), and \(\{s,t\}=\{(1,2),(2,3)\}\) or \(\{(1,3),(2,2)\}\) (see Figure 8d). Figure 6: A schematic diagram for (**a**) Statement (1), (**b**) Statement (2), (**c**) Statement (3), and (**d**) Statement (4) of Proposition 1, where the bold dashed lines indicate the cycles (paths) and \(\otimes\) represents the destruction of an edge while constructing a cycle or path. **Theorem 1** (See [17]). : _Assume that \(L(m,n;k,l)\) is a \(L\)-shaped supergrid graph with vertices \(s\) and \(t\). Then, \(HP(L(m,n;k,l),s,t)\) does exist if and only if \((L(m,n;k,l),s,t)\) does not satisfy conditions \((\mathrm{F1})\), \((\mathrm{F3})\), and \((\mathrm{F4})\)._  
The following lemma shows the Hamiltonicity of \(L\)-shaped supergrid graphs. **Theorem 2** (See [17]). : _Assume that \(L(m,n;k,l)\) is a \(L\)-shaped supergrid graph. Then, \(L(m,n;k,l)\) contains a Hamiltonian cycle if and only if it does not satisfy condition \((\mathrm{F5})\), where condition \((\mathrm{F5})\) is defined as follows:_  
\((\mathrm{F5})\) _there exists a vertex \(w\) in \(L(m,n;k,l)\) such that \(deg(w)=1\)._  
**Theorem 3** (See [12; 17]). : _Assume that \(G\) is \(R(m,n)\) or \(L(m,n;k,l)\) with two distinct vertices \(s\) and \(t\). Then, a longest \((s,t)\)-path in \(G\) can be computed in \(O(mn)\)-linear time._  
The Necessary and Sufficient Conditions for the Hamiltonicity and Hamiltonian Connectivity of \(C\)-Shaped Supergrid Graphs  
In this section, we will give the necessary and sufficient conditions for \(C\)-shaped supergrid graphs containing a Hamiltonian cycle and Hamiltonian \((s,t)\)-path. First, we will verify the Hamiltonicity of \(C\)-shaped supergrid graphs. If \(m-k=1\) or there exists a vertex \(w\in V(C(m,n;k,l;c,d))\) such that \(deg(w)=1\), then \(C(m,n;k,l;c,d)\) contains no Hamiltonian cycle. Therefore, \(C(m,n;k,l;c,d)\) is not Hamiltonian if condition \((\mathrm{F6})\) is satisfied, where condition \((\mathrm{F6})\) is defined as follows:  
\((\mathrm{F6})\): \(a(=m-k)=1\) or there exists a vertex \(w\in V(C(m,n;k,l;c,d))\) such that \(deg(w)=1\). **Theorem 4**. : \(C(m,n;k,l;c,d)\) _has a Hamiltonian cycle if and only if it does not satisfy condition \((\mathrm{F6})\)._  
Proof. : Only if part \((\Rightarrow)\): Assume that \(C(m,n;k,l;c,d)\) satisfies condition \((\mathrm{F6})\), then we will prove that it contains no Hamiltonian cycle. Let \(v\in V(C(m,n;k,l;c,d))\) such that \(c+1\leqslant v_{y}\leqslant c+l\) if \(a(=m-k)=1\); otherwise \(v\sim w\). It is obvious that any cycle  
Figure 8: \(L\)-shaped supergrid graph in which \(HP(L(m,n;k,l),s,t)\) does not exist, where **(a,b)** satisfy condition \((\mathrm{F1})\), **(c)** depicts condition \((\mathrm{F2})\), and **(d)** shows condition \((\mathrm{F3})\).