# Finding Hamiltonian and Longest \((s,t)\)-Paths of \(C\)-Shaped Supergrid Graphs in Linear Time
## 4 The Longest \((s,t)\)-Paths in C-Shaped Supergrid Graphs  
In this section, first for the cases where \(HP(C(m,n;k,l;c,d),s,t)\) does not exist, we give the upper bounds on the lengths of the longest paths between \(s\) and \(t\). Then, we show that these upper bounds are equal to the lengths of the longest path between \(s\) and \(t\). Notice that the isomorphic cases are omitted. In the following, we use \(\hat{L}(G,s,t)\) to denote the length of the longest \((s,t)\)-paths and \(\hat{U}(G,s,t)\) to indicate the upper bound on the length of the longest \((s,t)\)-paths, where \(G\) is a rectangular, \(L\)-shaped, or \(C\)-shaped supergrid graph. By the length of a path we mean the number of vertices visited by the path. These upper bounds are given in Lemmas 11-13. We first consider the case of \(a=1\), where \(a=m-k\). In this case, \((C(m,n;k,l;c,d),s,t)\) may satisfy conditions (F1), (F3), or (F9). We compute the upper bound of the longest \((s,t)\)-path in this case as the following lemma. Lemma 11: _Let \(a=1\) and \(w=(1,c+1)\). Assume that \(C(m,n;k,l;c,d),s,t)\) satisfies one of the conditions (F1), (F3), and (F9). Then, the following conditions hold:_  
1. _If_ \(s_{y},t_{y}>c\) _(resp.,_ \(s_{y},t_{y}\leqslant c\)_), then the length of any_ \((s,t)\)_-path cannot exceed_ \(\hat{L}(G_{1},s,t)\)_, where_ \(G_{1}=L(m,n-c;k,l)\) _(resp.,_ \(G_{1}=L(c+1,m;1,k)\)_) _(see Figure_ 19_,b)._
2. _If_ \((s_{y}\leqslant c\) _and_ \(t_{y}>c)\) _or_ \((t_{y}\leqslant c\) _and_ \(s_{y}>c)\)_, without loss of generality assume that_ \(s_{y}\leqslant c\)_, then the length of any_ \((s,t)\)_-path cannot exceed_ \(\hat{L}(G_{2},s,z)+\hat{L}(G_{1},w,t)\)_, where_ \(G_{2}=R(m,c)\)_,_ \(G_{1}=L(m,n-c;k,l)\)_, and_ \(z=(1,c)\) _if_ \(s\
eq(1,c)\)_; otherwise_ \(z=(2,c)\) _(see Figure_ 19c_,d)._  
Proof: The proof is straightforward, see Figure 19.  
Figure 18: (a,b) A vertical and horizontal separation on \(R_{1}\) under that \(s,t\in R_{1}\) and \(\{s,t\}\) is a vertex cut of \(R_{1}\), and (c) a Hamiltonian \((s,t)\)-path in \(C(m,n;k,l;c,d)\). Next, we consider the case of \(a\geqslant 2\). In this case, \((C(m,n;k,l;c,d),s,t)\) may satisfy conditions (F1), (F3), (F7), or (F8). Depending on the sizes of \(c\) and \(d\), we consider the subcases of (1) \(c,d\geqslant 2\) and (2) \(c=1\) or \(d=1\). Consider that \(c,d\geqslant 2\). Then, \((C(m,n;k,l;c,d),s,t)\) does not satisfy conditions (F3), (F7), and (F8). Thus, \((C(m,n;k,l;c,d),s,t)\) may satisfy condition (F1) only. We can see that \(s\) or \(t\) is not a cut vertex when \(a,c,d\geqslant 2\). Thus, \(\{s,t\}\) is a vertex cut when \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F1). We can see from the structure of \(C(m,n;k,l;c,d)\) that \(a\), \(c\), or \(d\) is equal to \(2\) if \(\{s,t\}\) is a vertex cut. The following lemma shows the upper bound of the longest \((s,t)\)-path under that \(a,c,d\geqslant 2\) and \((C(m,n;k,l;c,d),s,t)\) satisfies condition (F1). Lemma 12: _Assume that \(a,c,d\geqslant 2\) and \(\{s,t\}\) is a vertex cut. Then, the following conditions hold:_  
* _If_ \(a=2\) _and_ \(c+1\leqslant s_{y}=t_{y}\leqslant c+l\)_, then the length of any_ \((s,t)\)_-path cannot exceed_ \(\max\{\hat{L}(G_{11},s,t),\hat{L}(G_{12},s,t)\}\)_, where_ \(G_{11}=L(m,n^{\prime};k,l^{\prime})\)_,_ \(G_{12}=L(s_{y},m;k^{\prime},k)\)_,_ \(n^{\prime}=n-s_{y}+1\)_,_ \(l^{\prime}=n^{\prime}-d\)_, and_ \(k^{\prime}=s_{y}-1\) _(see Figure_ 20_,_b_)._
* _If_ \(k\geqslant 2\)_,_ \(a+1\leqslant s_{x},t_{x}\leqslant a+k-1(=m-1)\)_, and_ \([(c=2\) _and_ \(s_{y},t_{y}\leqslant c)\) _or_ \((d=2\)_, and_ \(s_{y},t_{y}\geqslant c+l)]\)_, without loss of generality assume that_ \(d=2\) _and_ \(s_{y},t_{y}\geqslant c+l\)_, then the length of any_ \((s,t)\)_-path cannot exceed_ \(\hat{L}(G_{1},s,t)+|V(G_{2})|=\hat{L}(G_{1},s,t)+k\times c\)_, where_ \(G_{1}=L(m,n;k,l+c)\) _and_ \(G_{2}=R(k,c)\) _(see Figure_ 20_,_d_)._  
Proof: Consider Figure 20a,b. Removing \(s\) and \(t\) clearly disconnects \(C(m,n;k,l;c,d)\) into two components \(G_{1}\) and \(G_{2}\).