Finding Hamiltonian and Longest (s, t)-paths of C-shaped Supergrid Graphs in Linear Time

Fatemeh Keshavarz-Kohjerdi; Ruo-Wei Hung

REVIEW 3 major objections 5 minor 55 references

Finding Hamiltonian and Longest (s, t)-paths of C-shaped Supergrid Graphs in Linear Time

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read C-shaped supergrid graphs: Hamiltonian paths fully classified

desk verdict A genuine first treatment of C-shaped supergrid graphs that deserves referee time, but the main sufficiency lemma has a stated parameter gap (c=2,d=1 and c=2,d=2) that needs to be fixed before Theorem 3.6 is fully proven. read the letter →

arxiv 1908.07447 v1 pith:NWGJOFG3 submitted 2019-08-17 cs.CC cs.DMmath.CO

Ruo-Wei Hung , Fatemeh Keshavarz-Kohjerdi This is my paper · ORCID

classification cs.CCcs.DMmath.CO MSC 05C4568Q2568R10

keywords HamiltonianpathcycleconnectivitylongestsupergridgraphsC-shapedlinear-timealgorithmcutvertex

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves the exact conditions under which a C-shaped supergrid graph—a rectangular grid of vertices with a rectangular block removed from one side, leaving a C-like shape—contains a Hamiltonian cycle and a Hamiltonian path between two prescribed vertices. It then gives an algorithm that constructs a longest path between any two distinct vertices in linear time in the number of cells. The main characterization is a short list of forbidden configurations: one cuts off a degree-one vertex or separates the endpoints, and the other four are small endpoint patterns that force a path to miss a vertex. If the results are correct, they settle the Hamiltonian and longest-path problems for this class of supergrid graphs with a rectangular hole, a step beyond the previously solved rectangle and L-shaped cases. Because Hamiltonian paths in general supergrid graphs are NP-complete, the positive result is a structural gain rather than a routine extension.

What carries the argument

The load-bearing objects are canonical Hamiltonian cycles and paths: Hamiltonian cycles of rectangular supergrid graphs that follow the boundary on three sides (flat faces) and deviate on one side (a concave face), and rectangular Hamiltonian $(s,t)$-paths that keep at least one boundary edge on each side. The proofs partition the C-shaped graph by vertical and horizontal separations into rectangular and L-shaped supergrid subgraphs, then glue Hamiltonian cycles or paths of the pieces using Proposition 2.5: two cycles, or a cycle and a path, with parallel edges across a separator can be spliced into one cycle or path. The flat-face orientation is what supplies those parallel edges. The forbidden conditions are collected from the cut-vertex/vertex-cut obstruction of Lemma 2.2 and from the endpoint patterns that survive because a too-narrow arm of the C cannot be traversed without revisiting a vertex.

What would settle it

Check the smallest nontrivial case of Lemma 3.4, the C-shaped graph $C(4,4;1,2;1,1)$ with $s=(2,2)$ and $t=(2,3)$: it has 14 vertices, and an exhaustive enumeration will either find a Hamiltonian $(s,t)$-path or not. If none exists, the constructive proof of Theorem 3.6 fails for that case; if one exists, the claimed gluing pattern is corroborated on the minimal example.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 3.6: a C-shaped supergrid graph $C(m,n;k,l;c,d)$ has a Hamiltonian $(s,t)$-path if and only if the pair does not satisfy any of five conditions (F1), (F3), (F7), (F8), and (F9). Condition (F1) says $s$ or $t$ is a cut vertex, or $\{s,t\}$ separates the graph; (F3) says there is a degree-one vertex other than $s,t$; (F7), (F8), and (F9) are explicit endpoint placements in narrow arms of the C. The paper also proves (Theorem 3.1) that the graph is Hamiltonian if and only if it avoids condition (F6), namely a one-column arm or any degree-one vertex. On top of these, Theorem 4.5 states that a longest $(s,t)$-path can be found in $O(mn)$ time. In the authors' phrasing, C-shaped supergrid graphs are Hamiltonian except when an arm is one column wide or a vertex has no way through, and Hamiltonian connected except for the five listed endpoint patterns.

Load-bearing premise

The proofs repeatedly assume that canonical Hamiltonian cycles and paths in rectangular and L-shaped supergrid graphs can always be oriented so that a flat face lies along a chosen separator edge; that orientation capability is asserted rather than explicitly proven in the cited constructions, and the gluing steps collapse without it.

Editorial extensions

If this is right

Every C-shaped supergrid graph with arms at least two columns wide and no degree-one vertex has a Hamiltonian cycle.
A Hamiltonian path between two prescribed endpoints exists in all but the five explicitly listed forbidden endpoint placements; outside those, the proof actually constructs the path.
A longest path between any two distinct vertices can be output in time linear in the number of vertices, not merely decided.
The same theorem yields an optimal stitching trace for computer embroidery on C-like shapes and a minimum printing trace for 3D printing a C-like component, the applications named in the paper.
Because the conditions are if-and-only-if, they give a linear-time certificate: checking the finite list of forbidden configurations decides Hamiltonicity or Hamiltonian connectivity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the flat-face orientation property holds in full generality, the same separation-and-gluing method should extend to other polyomino-shaped supergrid graphs whose rectangular decomposition yields at most L-shaped pieces, such as S-shaped or E-shaped holes, giving analogous if-and-only-if characterizations.
The forbidden endpoint lists in (F7), (F8), and (F9) all look like local separator obstructions; a natural conjecture is that every non-Hamiltonian-connected supergrid class fails only through cut vertices, degree-one vertices, or tiny endpoint-separator patterns of this kind.
A concrete stress test for the construction is to implement Lemma 3.4 on the smallest case, $C(4,4;1,2;1,1)$ with $s=(2,2)$ and $t=(2,3)$, and compare the constructed path against an exhaustive enumeration of all 14-vertex Hamiltonian $(s,t)$-paths.
The longest-path upper bounds in Lemmas 4.1–4.3 are expressed through already-solved rectangular and L-shaped instances; this suggests a recursive scheme for longer chains of holes, where each new hole adds one more level of previously solved subproblems.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

First thing you should know: this is a real result, not a repackaging, but the main sufficiency proof has a gap in Lemma 3.5 that needs to be closed before I'd trust Theorem 3.6 as stated. The authors characterize Hamiltonian cycles, Hamiltonian (s,t)-paths, and longest paths for C-shaped supergrid graphs—the first time this class with a boundary-touching rectangular hole gets treated. The techniques are inherited from their rectangular and L-shaped supergrid work, so novelty is incremental, but the class is nontrivial and the linear-time longest path algorithm is a concrete payoff. No fitting, no invented parameters; the self-citations point to genuinely prior published results, and I don't see circularity.

The soft spots are in the proof presentation. Lemma 3.5 assumes c > 1 or d > 1 but concludes existence only when c > 2 or d > 2. Those cannot both be right. Since Theorem 3.6 applies Lemma 3.5 to every a > 1 case not covered by Lemma 3.4, the c=2,d=1 and c=2,d=2 (and mirrored) configurations are left without a stated sufficiency argument. The proof itself actually seems to handle d=2 in Case 1.1 and Case 1.2, and the WLOG d > 1 symmetry covers c=2,d=1 after rotation, which makes me think this is a fixable typo in the lemma statement rather than a false theorem. But as written, the iff in Theorem 3.6 is not established for a nonempty family. The authors need to restate Lemma 3.5 cleanly and add a sentence explaining why the d=2 cases inside it are covered.

Second soft spot is heavier delegation than I'd like. Several subcases end with 'a simple check shows' or 'by similar arguments' and the figures carry the proof. In particular, the repeated claim that canonical cycles/paths can be oriented with a flat face toward a designated separator edge is asserted from earlier algorithms, but not stated as a lemma or proven here. That property is load-bearing for the gluing operation, and the authors should make the citation exact or add the missing statement. These are layout issues in a long case analysis, and I don't think they sink the result, but a referee would have to do real work to verify all of them.

Who is this for? Researchers working on Hamiltonian/longest paths in grid-like graphs, especially the supergrid literature. The applications to embroidery/3D printing stitching are plausible but not developed. I'd send it to a serious referee; the gap is specific and likely fixable. My recommendation: conditional acceptance, with the Lemma 3.5 statement fixed and the c=2 cases explicitly walked through.

Referee Report

3 major / 5 minor

Summary. The paper studies Hamiltonian cycles, Hamiltonian (s,t)-paths, and longest (s,t)-paths in C-shaped supergrid graphs, i.e., rectangular supergrid graphs from which a rectangular block has been removed so that the remaining shape is C-like. The main results are: (Theorem 3.1) a C-shaped supergrid graph has a Hamiltonian cycle iff it does not satisfy condition (F6); (Theorem 3.6) a Hamiltonian (s,t)-path exists iff the pair (C(m,n;k,l;c,d),s,t) avoids conditions (F1), (F3), (F7), (F8), and (F9); and (Theorem 4.5) a longest (s,t)-path can be computed in O(mn) linear time. The proofs are constructive and proceed by separating the graph into rectangular and L-shaped supergrid subgraphs, applying previously established Hamiltonian results, and gluing the resulting cycles and paths via Proposition 2.5. The longest-path section derives upper bounds for the forbidden cases and gives matching constructions.

Significance. If the results are correct, the paper provides a complete characterization of Hamiltonicity and Hamiltonian connectivity for a class of supergrid graphs with a hole, and it gives the first linear-time algorithm for the longest (s,t)-path problem in this class. This is a meaningful step beyond the previously solved rectangular and L-shaped cases, and it has concrete applications to embroidery and 3D-printing trace optimization. The paper is constructive and does not rely on numerical fitting or data-dependent parameters; it uses prior published theorems for rectangular and L-shaped supergrid graphs as building blocks. However, the proof is an extensive case analysis with many subcases delegated to figures, 'similar arguments', and 'simple checks', which makes verification difficult. More importantly, at least one parameter range needed by Theorem 3.6 is not actually covered by the stated Lemma 3.5, and the gluing arguments repeatedly assume an oriented face-placement property that is not stated in the cited prior results. These issues make the central characterization incomplete as written.

major comments (3)

[Section 3, Lemma 3.5 and Theorem 3.6] Lemma 3.5 is stated for graphs with c > 1 or d > 1, but its conclusion is restricted to 'a >= 2 and (c > 2 or d > 2)'. Theorem 3.6 then invokes Lemma 3.5 for the whole range c > 1 or d > 1. The cases c = 2 with d = 1, and c = 2 with d = 2, together with their mirrors, are not covered by Lemma 3.3 (which requires a = 1) or by Lemma 3.4 (which requires c = d = 1). The proof of Lemma 3.5 assumes without loss of generality that d > 1 and never explains why the cases with d = 1 and c = 2 should be excluded. For example, the graph C(3,4;1,1;2,1) has a = 2, c = 2, d = 1, and for endpoints not covered by (F7) it lies in the domain of Theorem 3.6 but outside the stated hypothesis of Lemma 3.5. Thus the if direction of the Hamiltonian-path characterization is not proven for a nonempty family of inputs, and Theorem 4.5 inherits the same gap. The lemma needs to be extended to the full range c > 1 or d > 1, or the theorem must be split with separate arguments for the missing cases.
[Section 3, Lemmas 3.4–3.5 and Proposition 2.5] Several gluing steps require a stronger property than what the cited theorems state. For instance, in Lemma 3.4, Case 2.1.1, the proof asserts that R2 contains a Hamiltonian (s,t)-path P2 'in which one edge e2 is placed to face R1' and that R1 contains a Hamiltonian cycle HC1 'such that its one flat face is placed to face R2'; analogous assertions occur in Lemma 3.5, Cases 1.1 and 1.2, and in Lemma 4.4, Cases 4 and 6. However, Theorem 2.8 and Theorem 2.9, as stated in this paper, only assert the existence of a Hamiltonian path and a Hamiltonian cycle, respectively, and Lemma 2.4 gives an oriented-edge property only for rectangular graphs, not for L-shaped graphs. Because the concatenation via Proposition 2.5(2) requires two edges e1 ≈ e2, the oriented face-placement property is load-bearing. If the prior constructions in [41] do indeed always provide such an orientation, the paper should either prove this or cite the exact statements; otherwise the gluing construction may fail.
[Section 4, Algorithm 4.1] The control flow of Algorithm 4.1 is incorrect for inputs that satisfy a forbidden condition. Step 1 outputs a Hamiltonian path whenever a = 1, and Steps 2 and 3 behave similarly for a > 1, without first checking whether (C,s,t) satisfies (F1), (F3), (F7), (F8), or (F9). Step 4 is therefore unreachable exactly for the inputs it is meant to handle. For example, if a = 1 and sy, ty <= c, condition (F9) holds and no Hamiltonian (s,t)-path exists, yet Step 1 would invoke Lemma 3.3 and return a Hamiltonian path. The guards in Steps 1–3 need to include the condition that none of the forbidden conditions holds, or Step 4 must be evaluated before the constructive lemmas are applied.

minor comments (5)

[Section 3, Lemma 3.4, Case 2.2] The definition of p and q in Case 2.2 has a final 'otherwise' branch that is ambiguous when more than one of the preceding conditions fails; the four combinations should be spelled out explicitly.
[Section 3, Lemma 3.5, Cases 2 and 3] The proof delegates Cases 2 and 3 to 'similar arguments' from Lemma 3.4, but the decomposition in Lemma 3.5 is structurally different because R1 is a rectangular graph rather than an L-shaped graph; the required arguments should be given rather than only referenced.
[Section 3, Lemma 3.2, condition (F7)] The proof of the necessity of (F7) says that existence is checked 'by inspecting all cases of Fig. 12(d)', but the figure appears to show only a representative configuration; a complete enumeration or a short parity/cut argument would make the necessity proof more transparent.
[Section 4, Lemma 4.3] In the proof of Lemma 4.3, the text reads 'For (FC14) and (F15)' where the second label should be (FC15); this typo should be corrected.
[Section 4, Lemma 4.1] The proof of Lemma 4.1 is stated as 'straightforward, see Fig. 21', but the upper-bound claims in (FC7) and (FC8) are used later in Theorem 4.5; a short justification for why no path can use vertices outside the indicated L-shaped subgraphs would improve the verifiability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the C-shaped Hamiltonian result is a new decomposition proof built on prior rectangular/L-shaped lemmas, not a restatement of its inputs.

full rationale

The paper does not fit parameters, rename a known result as a prediction, or define its target in terms of the conclusion. The central theorem (Theorem 3.6) is an iff characterization for C-shaped supergrid graphs, and its proof decomposes the graph into rectangular and L-shaped pieces whose Hamiltonian-path/cycle properties are imported from the authors' earlier work (Lemmas 2.1, 2.3, 2.6; Theorems 2.8, 2.9). Those citations are load-bearing, but they are independent prior structural statements and are not restatements of the C-shaped theorem itself; hence self-citation alone does not make the derivation circular. No step in the paper reduces by construction to its own input: the gluing operations in Proposition 2.5 are general graph-theoretic operations, and the forbidden conditions (F1), (F3), (F7), (F8), (F9) are separate from the sufficiency constructions. The reader's noted concern about Lemma 3.5 is a proof-coverage gap rather than circularity: Lemma 3.5 is stated for a ≥ 2 and (c > 2 or d > 2), while Theorem 3.6 applies it to all a ≥ 2 with c > 1 or d > 1, leaving cases such as c = 2, d = 1 or c = d = 2 without an explicit sufficiency argument. This is a correctness risk internal to the proof structure, not a circular dependence, and so it does not affect the circularity score. The derivation is self-contained in the relevant sense: given the cited rectangular and L-shaped results, the C-shaped claims are proven by new case analysis rather than assumed.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no free parameters or invented entities. It relies on standard graph theory and on prior published results for rectangular and L-shaped supergrid graphs, which are used as black boxes. The main new content is the case analysis that combines these components via separations and Proposition 2.5.

assumptions (5)

standard math Definitions of supergrid graphs, C-shaped graphs, Hamiltonian cycles and paths, and the separation operation (Section 2).
Basic graph-theoretic terminology and definitions, assumed without proof.
domain assumption Lemma 2.1 (Hamiltonicity of rectangular supergrid graphs, from [22]).
Used in Theorems 3.1 and throughout for the base rectangles in separations; taken as a black box from prior work.
domain assumption Lemma 2.3 (Hamiltonian connectivity of rectangular supergrid graphs, from [24]).
Used in Lemmas 3.3-3.5 to obtain Hamiltonian paths in rectangular subgraphs; cited as an established result.
domain assumption Theorem 2.8 and Theorem 2.9 (Hamiltonian paths and cycles in L-shaped supergrid graphs, from [27,41]).
Used to obtain Hamiltonian paths and cycles in L-shaped subgraphs after separations; cited from prior papers by the same authors.
domain assumption Theorem 2.10 (linear-time algorithm for longest paths in rectangular and L-shaped supergrid graphs, from [41]).
Used in Section 4 to compute the component lengths in the upper-bound formulas; cited as a previously published algorithm.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Finding Hamiltonian and Longest (s, t)-paths of C-shaped Supergrid Graphs in Linear Time." pith.science (2026). https://pith.science/paper/NWGJOFG3

@misc{pith2026190807447,
  author       = {Pith},
  title        = {Pith review of: Finding Hamiltonian and Longest (s, t)-paths of C-shaped Supergrid Graphs in Linear Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NWGJOFG3}},
  note         = {Machine review of arXiv:1908.07447}
}

read the original abstract

A supergrid graph is a finite vertex-induced subgraph of the infinite graph whose vertex set consists of all points of the plane with integer coordinates and in which two vertices are adjacent if the difference of their x or y coordinates is not larger than 1. The Hamiltonian path (cycle) problem is to determine whether a graph contains a simple path (cycle) in which each vertex of the graph appears exactly once. This problem is NP-complete for general graphs and it is also NP-complete for general supergrid graphs. Despite the many applications of the problem, it is still open for many classes, including solid supergrid graphs and supergrid graphs with some holes. A graph is called Hamiltonian connected if it contains a Hamiltonian path between any two distinct vertices. In this paper, first we will study the Hamiltonian cycle property of C-shaped supergrid graphs, which are a special case of rectangular supergrid graphs with a rectangular hole. Next, we will show that C-shaped supergrid graphs are Hamiltonian connected except few conditions. Finally, we will compute a longest path between two distinct vertices in these graphs. The Hamiltonian connectivity of C-shaped supergrid graphs can be applied to compute the optimal stitching trace of computer embroidery machines, and construct the minimum printing trace of 3D printers with a C-like component being printed.

Figures

Figures reproduced from arXiv: 1908.07447 by the authors.

**Figure 2.** (a) A rectangular supergrid graph, (b) a [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗

**Figure 3.** A rectangular supergrid graph R(m, n), where m = 10, n = 8, and the bold dashed lines indicate vertical and horizontal separations. m n l k (a) (b) m n l k c d a = m k - [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

Figures from the paper (26 more)

**Figure 4.** Figure 4: The structure of (a) L-shaped supergrid graph L(m, n; k, l), where k = 6, l = 8, m − k = 4, and n − l = 3 and (b) C-shaped supergrid graph C(m, n; k, l; c, d), where k = l = 6, c = 2, d = n − l − c = 3, and a = m − k = 4. (vx + 1, vy + 1), (vx + 1, vy − 1), and (vx − 1…

**Figure 5.** Figure 5: A canonical Hamiltonian cycle containing three flat faces and o [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]

**Figure 6.** Figure 6: Rectangular supergrid graphs in which there is no Hamiltonian ( [PITH_FULL_IMAGE:figures/full_fig_p006_6.png]

**Figure 7.** Figure 7: A schematic diagram for (a) Statement (1), (b) Statement [PITH_FULL_IMAGE:figures/full_fig_p007_7.png]

**Figure 8.** Figure 8: (a)–(o) The possible Hamiltonian (s, t)-path of R(3, 3) when s, t 6∈ {z1, z2, z3}, and (p) the construction of Hamiltonian (s, t)-path of R(k+ 1, 3) for k > 3 and s, t ∈ R˜, where the solid lines indicate the constructed Hamiltonian (s, t)-path and ⊗ represents the des…

**Figure 9.** Figure 9: L-shaped supergrid graph in which there is no Hamiltonian (s, t)-path for (a) s is a cut vertex, (b) {s, t} is a vertex cut, (c) there exists a vertex w such that deg(w) = 1, w 6= s, and w 6= t, and (d) m − k = 1, n − l = 2, l = 1, k > 2, and {s, t} = {(1, 2),(2, 3)}. …

**Figure 10.** Figure 10: (a) A vertical and horizontal separations on [PITH_FULL_IMAGE:figures/full_fig_p009_10.png]

**Figure 11.** Figure 11: (a) and (b) Hamiltonian cycles in R1 and R2, and (c) and (d) a Hamiltonian cycle in C(m, n; k, l; c, d) for [PITH_FULL_IMAGE:figures/full_fig_p010_11.png]

**Figure 12.** Figure 12: Some C-shaped supergrid graphs in which there is no Hamiltonian (s, t)-path. Now, we give necessary and sufficient conditions for the existence of a Hamiltonian (s, t)-path in C(m, n; k, l; c, d). In addition to condition (F1) (as depicted in [PITH_FULL_IMAGE:figures…

**Figure 13.** Figure 13: (a) A horizontal separation on C(m, n; k, l; c, d), (b) Hamiltonian paths P1 and P2 in (R1, s, p) and (R2, q, t), respectively, and (c) a Hamiltonian (s, t)-path in C(m, n; k, l; c, d), where a = 1 and bold lines indicate the constructed Hamiltonian path. (F8), consid…

**Figure 14.** Figure 14: (a)–(c) A vertical and horizontal separations on [PITH_FULL_IMAGE:figures/full_fig_p012_14.png]

**Figure 15.** Figure 15: (a) A vertical and horizontal separations on [PITH_FULL_IMAGE:figures/full_fig_p012_15.png]

**Figure 16.** Figure 16: (a)–(c) A horizontal separation on C(m, n; k, l; c, d) for a > 2, c = d = 1, and n > 3, (d) a Hamiltonian (s, t)-path in R2 and a Hamiltonian cycle in R1, and (e) a Hamiltonian (s, t)-path in C(m, n; k, l; c, d). Case 2.1: s, t ∈ R1 or s, t ∈ R2. Without loss of gener…

**Figure 17.** Figure 17: (a) The pattern for constructing a Hamiltonian ( [PITH_FULL_IMAGE:figures/full_fig_p013_17.png]

**Figure 18.** Figure 18: (a)–(c) A horizontal separation on C(m, n; k, l; c, d) under that a > 1 and d > 1, (d) a Hamiltonian (s, t)-path in R1 and a Hamiltonian cycle in R2 for s, t ∈ R1 and {s, t} is not a vertex cut of R1, and (e) a Hamiltonian (s, t)-path in C(m, n; k, l; c, d) for (d). C…

**Figure 19.** Figure 19: (a)–(c) A vertical and horizontal separations on [PITH_FULL_IMAGE:figures/full_fig_p015_19.png]

**Figure 20.** Figure 20: A Hamiltonian (s, t)-path in C(m, n; k, l; c, d) under that a, d > 1 and s, t ∈ R2. Case 3: (s ∈ R1 and t ∈ R2) or (s ∈ R2 and t ∈ R1). A Hamiltonian (s, t)-path of (C(m, n; k, l; c, d) can be constructed by similar arguments in proving Case 2.2 of Lemma 3.4. Notice t…

**Figure 21.** Figure 21: A longest path between s and t under that a = 1 for (a)–(b) (FC7) holds, and (c)–(d) (FC8) holds, where bold lines indicate the constructed longest (s, t)-path and bold dash lines indicate the separations. Proof. The proof is straightforward, see [PITH_FULL_IMAGE:fig…

**Figure 22.** Figure 22: A longest path between s and t under that a > 2 and c, d > 2 for (a)–(b) (FC9) holds, and (c)–(d) (FC10) holds, where bold lines indicate the constructed longest (s, t)-path. Lemma 4.2. Assume that a, c, d > 2 and {s, t} is a vertex cut. Then, the following conditions…

**Figure 23.** Figure 23: (a) The separations on C(m, n; k, l; c, d) for a > 2 and c = 1, (b) the case of s, t ∈ G2, (c) the case of s ∈ G1 and t ∈ G2, and (d) the case of s, t ∈ G1. Case III: s, t ∈ G1. In this case, (C(m, n; k, l; c, d), s, t) may satisfy condition (F1), (F3), (F7), or (F8),…

**Figure 24.** Figure 24: The cases for s, t ∈ G1 and {s, t} is a vertex cut of G1, where (a)–(b) {s, t} = {(a, 1),(a, 2)}, (c) a = 2, sy = ty and a + c 6 sx, tx 6 a + l, and (d) d = 2, k > 1, a < sx = tx < m and n − 1 6 sy, ty 6 n. Case III.2: {s, t} is a vertex cut of G1. Consider the follow…

**Figure 25.** Figure 25: The cases for s, t ∈ G1 and {s, t} is not a vertex cut of G1, where (a)–(b) a = 2, sy, ty 6 2, sy 6= ty, and sx 6= tx, (c)–(e) (C(m, n; k, l; c, d), s, t) satisfies condition (F8), and (f)–(g) (G1, s, t) satisfies condition (F3) but it does not satisfy condition (F1).…

**Figure 26.** Figure 26: The longest path between s and t under that a > 2 and c = 1, where (a)–(b) (FC11) holds and (c)–(d) (FC12) holds, where bold lines indicate the constructed longest (s, t)-path. (a) (b) (c) G11 s t (d) s t s t G12 s t s t (e) G11 s t (f) G12 G1 G1 [PITH_FULL_IMAGE:fig…

**Figure 27.** Figure 27: The longest path between s and t under that a > 2 and c = 1, where (a)–(b) (FC13) holds, (c)–(d) (FC14) holds, and (e)–(f) (FC15) holds. (a) (b) (c) s s t t s p t q p q p q (d) (e) t s a > 1 t s a > 2 t s a = 2 (f) s t (g) s t (h) Ga Gb Ga Gb Ga Gb r z r z r z w w G1 …

**Figure 28.** Figure 28: The longest path between s and t under that a > 2 and c = 1, where (a)–(c) (FC16) holds, (d)–(f) (FC17) holds, and (g)–(h) (FC18) holds. Lemma 4.3. Assume that a > 2 and c = 1. Let w = (a + 1, 1). Then, the following conditions hold: (FC11) If k > 1, a + 1 6 sx, tx 6 …

**Figure 29.** Figure 29: A longest (s, t)-path in C(m, n; k, l; c, d), where (FC18) holds. Case 6.1: s, t ∈ R1. A longest (s, t)-path of (C(m, n; k, l; c, d) can be constructed by similar arguments in proving Case 1 of Lemma 3.5 (see [PITH_FULL_IMAGE:figures/full_fig_p020_29.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

55 extracted references · 55 canonical work pages

[41]

The Hamiltonicity, Hamiltonian Connectivity, and Longest (s, t)-path of L-shaped Supergrid Graphs

F. Keshavarz-Kohjerdi, R.W. Hung, The Hamiltonicity, Hamiltonia n connectivity, and longest ( s, t )-path of L- shaped supergrid graphs, arXiv:1904.02581

work page Pith review arXiv 1904
[1]

N. Ascheuer, Hamiltonian path problems in the on-line optimization o f ﬂexible manufacturing systems, Technique Report TR 96-3, Konrad-Zuse-Zentrum f¨ ur Informationstechnik, Berlin, 1996

work page 1996
[2]

Bermond, Hamiltonian graphs, in Selected Topics in Graph Theo ry ed

J.C. Bermond, Hamiltonian graphs, in Selected Topics in Graph Theo ry ed. by L.W. Beinke and R.J. Wilson, Academic Press, New York, 1978

work page 1978
[3]

Bertossi, M.A

A.A. Bertossi, M.A. Bonuccelli, Hamiltonian circuits in interval graph generalizations, Inform. Process. Lett. 23 (1986) 195–200

work page 1986
[4]

Bondy, U.S.R

J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, Macmillan , London, 1976, Elsevier, New York

work page 1976
[5]

Bulterman, F.W

R.W. Bulterman, F.W. van der Sommen, G. Zwaan, T. Verhoeﬀ, A.J.M . van Gasteren, W.H.J. Feijen, On computing a longest path in a tree, Inform. Process. Lett. 81 (20 02) 93–96

work page
[6]

Chen, J.S

G.H. Chen, J.S. Fu, J.F. Fang, Hypercomplete: a pancyclic recurs ive topology for large scale distributed multi- computer systems, Networks 35 (2000) 56–69

work page 2000
[7]

S.D. Chen, H. Shen, R. Topor, An eﬃcient algorithm for construc ting Hamiltonian paths in meshes, Parallel Comput. 28 (2002) 1293–1305. 21

work page 2002

Show all 55 references

[8]

Chen, C.H

Y.C. Chen, C.H. Tsai, L.H. Hsu, J.J.M. Tan, On some super fault-tole rant Hamiltonian graphs, Appl. Math. Comput. 148 (2004) 729–741

2004
[9]

Damaschke, The Hamiltonian circuit problem for circle graphs is N P-complete, Inform

P. Damaschke, The Hamiltonian circuit problem for circle graphs is N P-complete, Inform. Process. Lett. 32 (1989) 1–2

1989
[10]

Ebrahimi, M

M. Ebrahimi, M. Daneshtalab, J. Plosila, Fault-tolerant routing a lgorithm for 3D NoC using hamiltonian path strategy, in: Proceedings of the Conference on Design, Automat ion and Test in Europe (DATE’13), 2013, pp. 1601–1604

2013
[11]

Fu, Hamiltonian connectivity of the WK-recursive with faulty nodes, Inform

J.S. Fu, Hamiltonian connectivity of the WK-recursive with faulty nodes, Inform. Sci. 178 (2008) 2573–2584

2008
[12]

Garey, D.S

M.R. Garey, D.S. Johnson, Computers and Intractability: A Guid e to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979

1979
[13]

Golumbic, Algorithmic Graph Theory and Perfect Graphs, Se cond edition, Annals of Discrete Mathematics 57, Elsevier, 2004

M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Se cond edition, Annals of Discrete Mathematics 57, Elsevier, 2004

2004
[14]

Gordon, Y.L

V.S. Gordon, Y.L. Orlovich, F. Werner, Hamiltonian properties of triangular grid graphs, Discrete Math. 308 (2008) 6166–6188

2008
[15]

Grebinski, G

V. Grebinski, G. Kucherov, Reconstructing a Hamiltonian cycle b y querying the graph: Application to DNA physical mapping, Discrete Appl. Math. 88 (1998) 147–165

1998
[16]

Gutin, Finding a longest path in a complete multipartite digraph, SIAM J

G. Gutin, Finding a longest path in a complete multipartite digraph, SIAM J. Discrete Math. 6(2) (1993) 270–273

1993
[17]

Hsieh, C.N

S.Y. Hsieh, C.N. Kuo, Hamiltonian-connectivity and strongly Hamilt onian-laceability of folded hypercubes, Com- put. Math. Appl. 53 (2007) 1040–1044

2007
[18]

Huang, M.Y

W.T. Huang, M.Y. Lin, J.M. Tan, L.H. Hsu, Fault-tolerant ring embe dding in faulty crossed cubes, in: Proceedings of World Multiconference on Systemics, Cybernetics, and Informa tics (SCI’2000), 2000, pp. 97–102

2000
[19]

Huang, J.J.M

W.T. Huang, J.J.M. Tan, C.N. Huang, L.H. Hsu, Fault-tolerant Ham iltonicity of twisted Cubes, J. Parallel Distrib. Comput. 62 (2002) 591–604

2002
[20]

Fang, The pancyclicity and the Hamiltonian-conne ctivity of the generalized base- b hypercube, Comput

C.H Huang, J.F. Fang, The pancyclicity and the Hamiltonian-conne ctivity of the generalized base- b hypercube, Comput. Electr. Eng. 34 (2008) 263–269

2008
[21]

Hung, Constructing two edge-disjoint Hamiltonian cycles an d two-equal path cover in augmented cubes, IAENG Intern

R.W. Hung, Constructing two edge-disjoint Hamiltonian cycles an d two-equal path cover in augmented cubes, IAENG Intern. J. Comput. Sci. 39 (2012) 42–49

2012
[22]

Hung, C.C

R.W. Hung, C.C. Yao, S.J. Chan, The Hamiltonian properties of sup ergrid graphs, Theoret. Comput. Sci. 602 (2015) 132–148

2015
[23]

Hung, Hamiltonian cycles in linear-convex supergrid graphs, Discrete Appl

R.W. Hung, Hamiltonian cycles in linear-convex supergrid graphs, Discrete Appl. Math. 211 (2016) 99–112

2016
[24]

Hung, C.F

R.W. Hung, C.F. Li, J.S. Chen, Q.S. Su, The Hamiltonian connectivity of rectangular supergrid graphs, Discrete Optim. 26 (2017) 41–65

2017
[25]

Hung, H.D

R.W. Hung, H.D. Chen, S.C. Zeng, The Hamiltonicity and Hamiltonian c onnectivity of some shaped supergrid graphs, IAENG Intern. J. Comput. Sci. 44 (2017) 432–444

2017
[26]

Hung, J.L

R.W. Hung, J.L. Li, C.H. Lin, The Hamiltonian connectivity of some alp habet supergrid graphs, in: The 2017 IEEE 8th International Conference on Awareness Science and Te chnology (iCAST’2017), Taichung, Taiwan, 2017, pp. 27–34

2017
[27]

Hung, J.L

R.W. Hung, J.L. Li, C.H. Lin, The Hamiltonicity and Hamiltonian connec tivity of L-shaped supergrid graphs, in: Lecture Notes in Engineering and Computer Science: Proceeding s of The International MultiConference of Engineers and Computer Scientists (IMECS’2018), Hong Kong, vo...

2018
[28]

Ioannidou, G.B

K. Ioannidou, G.B. Mertzios, S.D. Nikolopoulos, The longest path problem has a polynomial solution on interval graphs, Algorithmica 61 (2011) 320–341

2011
[29]

Itai, C.H

A. Itai, C.H. Papadimitriou, J.L. Szwarcﬁter, Hamiltonian paths in grid graphs, SIAM J. Comput. 11 (1982) 676–686. 22

1982
[30]

Johnson, The NP-complete column: An ongoing guide, J

D.S. Johnson, The NP-complete column: An ongoing guide, J. Algo rithms, 6 (1985) 434–451

1985
[31]

J. Jwo, S. Lakshmivarahan, S.K. Dhall, A new class of interconne ction networks based on the alternating group, Networks 23 (1993) 315–326

1993
[32]

Karger, R

D. Karger, R. Montwani, G.D.S. Ramkumar, On approximating the longest path in a graph, Algorithmica 18(1) (1997) 82–98

1997
[33]

Keshavarz-Kohjerdi, A

F. Keshavarz-Kohjerdi, A. Bagheri, Hamiltonian paths in some c lasses of grid graphs, J. Appl. Math. 2012 (2012), article no. 475087

2012
[34]

Keshavarz-Kohjerdi, A

F. Keshavarz-Kohjerdi, A. Bagheri, A. Asgharian-Sardroud , A linear-time algorithm for the longest path problem in rectangular grid graphs, Discrete Appl. Math. 160 (2012) 210–2 17

2012
[35]

Keshavarz-Kohjerdi, A

F. Keshavarz-Kohjerdi, A. Bagheri, An eﬃcient parallel algorit hm for the longest path problem in meshes, The J. Supercomput. 65 (2013) 723–741

2013
[36]

Keshavarz-Kohjerdi, A

F. Keshavarz-Kohjerdi, A. Bagheri, Hamiltonian paths in L-shaped grid graphs, Theoret. Comput. Sci. 621 (2016) 37–56

2016
[37]

Keshavarz-Kohjerdi, A

F. Keshavarz-Kohjerdi, A. Bagheri, A linear-time algorithm for ﬁnding Hamiltonian ( s, t )-paths in odd-sized rectangular grid graphs with a rectangular hole, The J. Supercomp ut. 73(9) (2017) 3821–3860

2017
[38]

Keshavarz-Kohjerdi, A

F. Keshavarz-Kohjerdi, A. Bagheri, A linear-time algorithm for ﬁnding Hamiltonian ( s, t )-paths in even-sized rectangular grid graphs with a rectangular hole, Theoret. Comput . Sci. 690 (2017), 26–58

2017
[39]

Keshavarz-Kohjerdi, A

F. Keshavarz-Kohjerdi, A. Bagheri, Longest ( s, t )-path in L-shaped grid graphs, Opti. Methods Softw. 34 (2018) 797–826

2018
[40]

Keshavarz-Kohjerdi, R.W

F. Keshavarz-Kohjerdi, R.W. Hung, G.H. Qiu, The longest ( s, t )-paths of C-shaped supergrid graphs, in: Lecture Notes in Engineering and Computer Science: International MultiCon ference of Engineers and Computer Scientists 2019 (IMECS’2019), Hong Kong, 2019, pp. 87–93

2019
[42]

Krishnamoorthy, An NP-hard problem in bipartite graphs, S IGACT News 7 (1976) 26

M.S. Krishnamoorthy, An NP-hard problem in bipartite graphs, S IGACT News 7 (1976) 26

1976
[43]

Lenhart, C

W. Lenhart, C. Umans, Hamiltonian cycles in solid grid graphs, in: P roceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS’97), 1997, pp. 496–50 5

1997
[44]

Y. Li, S. Peng, W. Chu, Hamiltonian connectedness of recursive dual-net, in: Proceedings of the 9th IEEE International Conference on Computer and Information Techno logy (CIT’09), vol. 1, 2009, pp. 203–208

2009
[45]

Liu, H.M

M. Liu, H.M. Liu, The edge-fault-tolerant Hamiltonian connectivit y of enhanced hypercube, in: International Conference on Network Computing and Information Security (NCI S’2011), vol. 2, 2011, pp. 103–107

2011
[46]

R.S. Lo, G.H. Chen, Embedding Hamiltonian paths in faulty arrange ment graphs with the backtracking method, IEEE Trans. Parallel Distrib. Syst. 12 (2001) 209–222

2001
[47]

Mertzios, D.G

G.B. Mertzios, D.G. Corneil, A simple polynomial agorithm for the lon gest path problem on cocomparability graphs, SIAM J. Discrete Math. 26 (2012) 940–963

2012
[48]

O’Callaghan, Computing the perceptual boundaries of dot p atterns, Comput

J.F. O’Callaghan, Computing the perceptual boundaries of dot p atterns, Comput. Graphics Image Process. 3 (1974) 141–162

1974
[49]

Park, K.Y

C.D. Park, K.Y. Chwa, Hamiltonian properties on the class of hype rcube-like networks, Inform. Process. Lett. 91 (2004) 11–17

2004
[50]

Preperata, M.I

F.P. Preperata, M.I. Shamos, Computational Geometry: An In troduction, Springer, New York, 1985

1985
[51]

J.R. Reay, T. Zamﬁrescu, Hamiltonian cycles in T -graphs, Discrete Comput. Geom. 24 (2000) 497–502

2000
[52]

Salman, Contributions to Graph Theory, Ph.D

A.N.M. Salman, Contributions to Graph Theory, Ph.D. thesis, Univ ersity of Twente, 2005

2005
[53]

Toussaint, Pattern recognition and geometrical complexit y, in: Proceedings of the 5th International Confer- ence on Pattern Recognition, Miami Beach, 1980, pp

G.T. Toussaint, Pattern recognition and geometrical complexit y, in: Proceedings of the 5th International Confer- ence on Pattern Recognition, Miami Beach, 1980, pp. 1324–1347. 23

1980
[54]

Uehara, Y

R. Uehara, Y. Uno, On computing longest paths in small graph cla sses, Int. J. Found. Comput. Sci. 18 (2007) 911–930

2007
[55]

Zamﬁrescu, T

C. Zamﬁrescu, T. Zamﬁrescu, Hamiltonian properties of grid gr aphs, SIAM J. Discrete Math. 5 (1992) 564–570. 24

1992

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [41]

The Hamiltonicity, Hamiltonian Connectivity, and Longest (s, t)-path of L-shaped Supergrid Graphs

F. Keshavarz-Kohjerdi, R.W. Hung, The Hamiltonicity, Hamiltonia n connectivity, and longest ( s, t )-path of L- shaped supergrid graphs, arXiv:1904.02581

work page Pith review arXiv 1904

[2] [1]

N. Ascheuer, Hamiltonian path problems in the on-line optimization o f ﬂexible manufacturing systems, Technique Report TR 96-3, Konrad-Zuse-Zentrum f¨ ur Informationstechnik, Berlin, 1996

work page 1996

[3] [2]

Bermond, Hamiltonian graphs, in Selected Topics in Graph Theo ry ed

J.C. Bermond, Hamiltonian graphs, in Selected Topics in Graph Theo ry ed. by L.W. Beinke and R.J. Wilson, Academic Press, New York, 1978

work page 1978

[4] [3]

Bertossi, M.A

A.A. Bertossi, M.A. Bonuccelli, Hamiltonian circuits in interval graph generalizations, Inform. Process. Lett. 23 (1986) 195–200

work page 1986

[5] [4]

Bondy, U.S.R

J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, Macmillan , London, 1976, Elsevier, New York

work page 1976

[6] [5]

Bulterman, F.W

R.W. Bulterman, F.W. van der Sommen, G. Zwaan, T. Verhoeﬀ, A.J.M . van Gasteren, W.H.J. Feijen, On computing a longest path in a tree, Inform. Process. Lett. 81 (20 02) 93–96

work page

[7] [6]

Chen, J.S

G.H. Chen, J.S. Fu, J.F. Fang, Hypercomplete: a pancyclic recurs ive topology for large scale distributed multi- computer systems, Networks 35 (2000) 56–69

work page 2000

[8] [7]

S.D. Chen, H. Shen, R. Topor, An eﬃcient algorithm for construc ting Hamiltonian paths in meshes, Parallel Comput. 28 (2002) 1293–1305. 21

work page 2002