# 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
Case III.3.2.2: \((c=1\) and \(\{s,t\}\
eq\{(1,1),(2,2)\}\) and \(\{(1,2),(2,1)\}\) or \((d=1\) and \(\{s,t\}\
eq\{(1,n),(2,n-1)\}\) and \(\{(1,n-1),(2,n)\}\)) (see Figure 23e,f). Based on the above cases, we compute the upper bounds of the longest \((s,t)\)-paths on \((C(m,n;k,l;c,d),s,t)\) under that \(a\geqslant 2\) and \(c=1\) as the following lemma. Lemma 13: _Assume that \(a\geqslant 2\) and \(c=1\). Let \(w=(a+1,1)\). Then, the following conditions hold:_  
* _If_ \(k>1\)_,_ \(a+1\leqslant s_{x},t_{x}\leqslant m\)_, and_ \((s_{y}=t_{y}=1\) _or_ \(s_{y}=t_{y}=n)\)_, then the length of any_ \((s,t)\)_-path cannot exceed_ \(t_{x}-s_{x}+1\) _(see Figure_ 24_a,b, and refer to Case I and Case III.1_)._
* _If_ \(t_{x}>1\)_,_ \(t_{y}=1\)_, and_ \([(s_{x}\leqslant a)\) _or_ \((s_{y}>a\) _and_ \(s_{y}>c+l)]\)_, then the length of any_ \((s,t)\)_-path cannot exceed_ \(\hat{L}(G_{1},s,z)+\hat{L}(G_{2},w,t)\)_, where_ \(G_{1}=L(m,n;k,l+c)\)_,_ \(G_{2}=R(k,c)\)_, and_ \(z=(a,1)\) _if_ \(s\
eq(a,1)\)_; otherwise_ \(z=(a,2)\) _(see Figure_ 24_c,d, and refer to Cases II and III.1_)._
* _If_ \(\{s,t\}=\{(a,1),(a,2)\}\) _(resp.,_ \(d=1\) _and_ \(\{s,t\}=\{(a,n-1),(a,n)\}\)_), then the length of any_ \((s,t)\)_-path cannot exceed_ \(\hat{L}(G_{1},s,t)\)_, where_ \(G_{1}=L(m,n;k,l+c)\) _(resp.,_ \(G_{1}=L(n,m;l+d,k)\)_) (see Figure_ 25_a,b, and refer to Case III.2.1_)._
* _If_ \(a=2\)_,_ \(s_{y}=t_{y}\)_, 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_ 25_c,d, and refer to Case III.2.2_)._
* _If_ \(d=2\)_,_ \(k>1\)_,_ \(a<s_{x}=t_{x}<m\)_, and_ \(n-1\leqslant s_{y},t_{y}\leqslant n\)_, 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}=C(m^{\prime},n;k^{\prime},l;c,d)\)_,_ \(G_{12}=R(m-m^{\prime}+1,d)\)_,_ \(m^{\prime}=s_{x}\)_, and_ \(k^{\prime}=m^{\prime}-a\) _(see Figure_ 25_e,f, and refer to Case III.2.3_)._
* _If_ \(a=2\) _and_ \((\{s,t\}=\{(1,1),(2,2)\}\) _or_ \(\{(1,2),(2,1)\})\) _(resp.,_ \(d=1\) _and_ \(\{s,t\}=\{(1,n),(2,n-1)\}\) _or_ \(\{(1,n-1),(2,n)\}\)_), then the length of_ \((s,t)\)_-path cannot exceed_ \(\hat{L}(G_{1},s,t)\)_, where_ \(G_{1}=L(m,n;k,l+c)\) _(resp.,_ \(G_{1}=L(n,m;l+d,k)\)_) (see Figure_ 26_a-c, and refer to Case III.3.1.1_ and Case III.3.2.1_)._
* _If_ \((C(m,n;k,l;c,d),s,t)\) _satisfies condition (_F8_), then the length of_ \((s,t)\)_-path cannot exceed_ \(\hat{L}(G_{1},s,t)\)_, where_ \(G_{1}=L(m,n;k,l+c)\) _(see Figure_ 26_d-f, and refer to Case III.3.1.2_)._
* _If_ \((C(m,n;k,l;c,d),s,t)\) _does not satisfy condition (_F1_),_ \(k>1\)_, and_ \([(a>2)\) _or_ \((a=2,\{s_{y},t\}\
eq\{(1,1),(2,2)\}\) _and_ \(\{(1,2),(2,1)\})\) _(resp.,_ \(d=1\) _and_ \(\{s,t\}\
eq\{(1,n),(2,n-1)\}\) _and_ \(\{(1,n-1),(2,n)\}\)_), then the length of any_ \((s,t)\)_-path cannot exceed_ \(\hat{L}(G_{1},s,t)+1\)_, where_ \(G_{1}=L(m,n;k,l+c)\) _(resp.,_ \(G_{1}=L(n,m;l+d,k)\)_) (see Figure_ 26_g,h, and refer to Case III.3.2.2_)._  
Figure 24: The longest \((s,t)\)-path under that \(a\geqslant 2\) and \(c=1\), where (**a,b**) (UB5) holds and (**c,d**) (UB6) holds, where the bold lines indicate the constructed longest \((s,t)\)-path. Proof. : For (UB5), consider Figure 24a,b. There is only one single path between \(s\) and \(t\) that has the specified. For (UB6), consider Figure 24c,d. Since \(c=1\) and \(w\) is a cut vertex, it is clear that the length of any \((s,t)\)-path cannot exceed \(\hat{L}(G_{1},s,z)+\hat{L}(G_{2},w,t)\). For (UB7), consider Figure 25a,b. In Figure 25a,b, \(\{s,t\}\) is a vertex cut and hence removing \(s\) and \(t\) clearly disconnects \(C(m,n;k,l;c,d)\) into two components. Thus, a simple path between \(s\) and \(t\) can only go through one of these components. Therefore, its length cannot exceed the size of the largest component.