# Finding Hamiltonian and Longest \((s,t)\)-Paths of \(C\)-Shaped Supergrid Graphs in Linear Time
## 2 Terminologies and Background Results
For cases (1)-(2) of condition (F8), consider Figure 11e,f. Let \(v\) be a vertex depicted in these figures. Since \(\{s,t,v\}\) is a vertex cut of \(C(m,n;k,l;c,d)\), then \(C(m,n;k,l;c,d)-\{s,t,v\}\) is disconnected and contains three (or two) components in which two components (or one component) consist of only one vertex. Hence, any path between \(s\) and \(t\) must pass through \(s\) or \(v\) twice. Therefore, \(C(m,n;k,l;c,d)\) contains no Hamiltonian \((s,t)\)-path. For case (3) of condition (F8), consider Figure 11g. A simple check shows that there is no Hamiltonian \((s,t)\)-path in \(C(m,n;k,l;c,d)\) containing both of vertices \(u\) and \(v\). For condition (F9), consider Figure 11h. Let \(v\in V(C(m,n;k,l;c,d)\) such that \(v_{x}=1\) and \(c+1\leqslant v_{y}\leqslant c+l\). Since \(a=1\), \(v\) is a cut vertex of \(C(m,n;k,l;c,d)\). Obviously, any path between \(s\) and \(t\) must pass through \(v\) two times. Therefore, \(C(m,n;k,l;c,d)\) contains no Hamiltonian \((s,t)\)-path. In the following, we will show that \(C(m,n;k,l;c,d)\) has a Hamiltonian \((s,t)\)-path when \((C(m,n;k,l;c,d),s,t)\) does not satisfy conditions (F1), (F3), (F7), (F8), and (F9). We consider the case of \(a=1\) in Lemma 8 and the case of \(a\geqslant 2\) in Lemmas 9 and 10. **Lemma 8**. : _Assume that \(a(=m-k)=1\) and \((C(m,n;k,l;c,d),s,t)\) does not satisfy conditions \((\)F1\()\), \((\)F3\()\), and \((\)F9\()\). Then \(HP(C(m,n;k,l;c,d),s,t)\) does exist._  
Proof. : Notice that, here, \((s_{y}\leqslant c\) and \(t_{y}>c+l)\) or \((t_{y}\leqslant c\) and \(s_{y}>c+l)\). If \(s_{y},t_{y}\leqslant c\), \(s_{y},t_{y}>c+l\), or \(c+1\leqslant s_{y}(\text{or }t_{y})\leqslant c+l\), then \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F1) or (F9). Without loss of generality, assume that \(s_{y}\leqslant c\) and \(t_{y}>c+l\). We make a horizontal separation on \(C(m,n;k,l;c,d)\) to obtain two disjoint subgraphs \(R_{1}=R(m,c)\)  
Figure 2:0 Some \(C\)-shaped supergrid graphs in which \(HP(C(m,n;k,l;c,d),s,t)\) does not exist, where (**a**,**b**) satisfy condition (F1), (**c**) depicts condition (F3), (**d**) depicts condition (F7), (**e**-**g**) depicts condition (F8), and (**h**) shows condition (F9). \(R_{2}=L(m,n-c;k,l)\). Let \(p\in V(R_{1})\) and \(q\in V(R_{2})\) such that \(p\sim q\), \(q=(1,c+1)\), and \(p=(1,c)\) if \(s\
eq(1,c)\); otherwise \(p=(2,c)\) (see Figure 12a). Consider \((R_{1},s,p)\). Condition (F1) holds, if  
1. \(c=1,k>1\), and \(s_{x}\
eq m\). Clearly, if this case holds, then \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F1), a contradiction. 2. \(c=2\) and \(s_{x}=p_{x}\geqslant 2\). Clearly, in this case, \(s_{x}=p_{x}=2\). It contradicts that \(p=(1,c)\) when \(s\
eq(1,c)\). Therefore, \((R_{1},s,p)\) does not satisfy condition (F1). Now, consider \((R_{2},q,t)\). Since \(q_{y}=c+1\) and \(t_{y}>c+l\), it is enough to show that \((R_{2},q,t)\) does not satisfy condition (F1). Condition (F1) holds, if \(d=1\), \(k>1\), and \(t_{x}\
eq m\). Clearly, if this case holds, then \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F1), a contradiction. Therefore, \((R_{2},q,t)\) does not satisfy conditions (F1), (F3), and (F4). Since \((R_{1},s,p)\) and \((R_{2},q,t)\) do not satisfy conditions (F1), (F3), and (F4), by Lemma 3 and Theorem 1, there exist Hamiltonian \((s,p)\)-path \(P_{1}\) and Hamiltonian \((q,t)\)-path \(P_{2}\) of \(R_{1}\) and \(R_{2}\), respectively (see Figure 12b). Then, \(P=P_{1}\Rightarrow P_{2}\) forms a Hamiltonian \((s,t)\)-path of \(C(m,n;k,l;c,d)\), as depicted in Figure 12c. Lemma 9: _Assume \(c=d=1\), \(a(=m-k)>1\), and \((C(m,n;k,l;c,d),s,t)\) does not satisfy conditions (F1), (F3), (F7), and (F8). Then \(HP(C(m,n;k,l;c,d),s,t)\) does exist._  
Proof: Depending on whether \(n=3\), we consider the following cases:  
Case 1: \(n=3\). Notice that, here, if \(k>1\), then \(s_{x}=t_{x}=m\). If \(k>1\) and \(s_{x}\
eq m\) and \(t_{x}\
eq m\), then \((C(m,n;k,l;c,d),s,t)\) satisfies (F1) or (F3).