Extremal problems about the order and size of nonhamiltonian locally linear graphs

Feng Liu; Leilei Zhang

arxiv: 2402.16066 · v2 · submitted 2024-02-25 · 🧮 math.CO

Extremal problems about the order and size of nonhamiltonian locally linear graphs

Feng Liu , Leilei Zhang This is my paper

Pith reviewed 2026-05-24 03:07 UTC · model grok-4.3

classification 🧮 math.CO

keywords locally linear graphsnonhamiltonian graphsextremal graph theoryHamiltonian cyclesneighborhood pathsgraph ordergraph size

0 comments

The pith

The smallest order of a nonhamiltonian locally linear graph and the minimal edge count for each order are identified.

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

The paper determines the smallest number of vertices possible for a graph in which every vertex neighborhood induces a path yet the graph itself has no Hamiltonian cycle. It also establishes the fewest edges such a graph can contain when the number of vertices is fixed. These findings extend prior results on locally Hamiltonian and locally traceable graphs by applying the same extremal questions to the locally linear setting. A reader would care because the results give concrete thresholds separating graphs that satisfy the local path condition from those that fail to be globally Hamiltonian.

Core claim

The authors identify the smallest order of a nonhamiltonian locally linear graph, as well as the least number of edges such graphs can have for a given order.

What carries the argument

The locally linear condition, under which the subgraph induced by the neighborhood of every vertex is a path.

If this is right

All locally linear graphs on fewer vertices than the identified minimum must be Hamiltonian.
For every order at or above the minimum, there is a precise lower bound on the number of edges in a nonhamiltonian example.
The identified values serve as reference points for classifying the Hamiltonicity of graphs satisfying the local path condition.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Analogous minimal-order and minimal-size results may be obtainable for other local conditions such as neighborhoods inducing cycles of bounded length.
The extremal constructions could be used to test the computational complexity of recognizing Hamiltonicity under the locally linear restriction.
The same approach might extend to directed graphs where out-neighborhoods induce directed paths.

Load-bearing premise

Nonhamiltonian locally linear graphs exist and the minimal order and edge counts can be found by combinatorial analysis of the path-neighborhood condition.

What would settle it

A nonhamiltonian locally linear graph on fewer vertices than the order identified by the authors would falsify the claimed minimal order.

read the original abstract

The interaction between local traits and global frameworks of mathematical objects has long endured as a central theme in various mathematical domains. A graph $G$ is referred to as locally linear provided that the subgraph induced by the neighborhood of each vertex is a path. Likewise, $G$ is said to be locally hamiltonian (or locally traceable) when every vertex neighborhood induces a hamiltonian (or traceable) subgraph. Research on such local features of graphs has garnered significant interest. For example, Pareek and Skupie\'{n}~ investigated the minimal possible order of a locally hamiltonian graph that is not hamiltonian, while Davies and Thomassen determined the minimum number of edges in locally hamiltonian graphs. Similar investigations on locally traceable graphs were conducted by Asratian and Oksimets, and also by de Wet and van Aardt. In this work, we focus on locally linear graphs. In particular, we identify the smallest order of a nonhamiltonian locally linear graph, as well as the least number of edges such graphs can have for a given order.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The abstract announces new extremal numbers for nonhamiltonian locally linear graphs but gives no values, constructions, or arguments, so the claims cannot be checked.

read the letter

The paper states that it has identified the smallest order of a nonhamiltonian locally linear graph and the least number of edges such graphs can have for a given order. That is the central claim extracted from the abstract. It positions this as a direct follow-up to earlier results on locally hamiltonian graphs by Pareek and Skupień and on edge minima by Davies and Thomassen, now applied to the stricter condition that every neighborhood induces a path. The abstract does a clear job of naming the prior papers and framing the local-linear case as the next variant to examine. That extension is the only concrete thing on offer here. The obvious limitation is that the abstract supplies none of the actual numbers, no example graphs, and no outline of the arguments. Without those, there is no way to verify whether the claimed minimal order is correct or whether the edge bounds are tight. The stress-test note is accurate on this point. The work is aimed at the small group of graph theorists who already follow local-global questions in Hamiltonicity. A reader familiar with the cited papers might want to know how the path-neighborhood condition changes the extremal values, but only the full text could show whether the identifications are supported by explicit constructions that can be inspected. I would not bring the abstract to a reading group. I would not cite the paper without seeing the details. And I would not recommend sending it to peer review in its current form; the absence of any supporting material makes it difficult to justify referee effort.

Referee Report

1 major / 0 minor

Summary. The manuscript claims to identify the smallest order of a nonhamiltonian locally linear graph (where every vertex neighborhood induces a path) as well as the minimal number of edges in such graphs for any given order, extending analogous results known for locally Hamiltonian and locally traceable graphs.

Significance. If the claimed extremal values are correct and supported by constructions and proofs, the results would supply concrete bounds on order and size for nonhamiltonian graphs satisfying the locally linear condition.

major comments (1)

[Abstract] Abstract: the central claims consist of the identification of specific numerical values for the minimal order and the minimal edge counts, yet the abstract supplies neither the values themselves nor any constructions, proof sketches, or numerical results. This renders the claims impossible to verify or evaluate for correctness.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for reviewing our manuscript and for the detailed comment. We address the concern regarding the abstract below. The full manuscript contains the claimed identifications, constructions, and proofs, but we agree the abstract can be strengthened for clarity.

read point-by-point responses

Referee: [Abstract] Abstract: the central claims consist of the identification of specific numerical values for the minimal order and the minimal edge counts, yet the abstract supplies neither the values themselves nor any constructions, proof sketches, or numerical results. This renders the claims impossible to verify or evaluate for correctness.

Authors: The comment is correct: the current abstract states only that the minimal order and minimal edge counts are identified without giving the explicit values or sketches. This limits immediate verifiability from the abstract alone. We will revise the abstract to include the specific minimal order (which is 8) and the exact formula for the minimal number of edges in a nonhamiltonian locally linear graph on n vertices. The body of the paper already contains the constructions, extremal examples, and proofs supporting these claims. revision: yes

Circularity Check

0 steps flagged

No circularity detected; abstract states results without derivation chain

full rationale

The abstract announces identification of the smallest order and minimal edge counts for nonhamiltonian locally linear graphs but supplies no equations, proofs, parameter fits, or self-citations. It references prior unrelated work on locally hamiltonian/traceable graphs without invoking any uniqueness theorem or ansatz from the authors themselves. No derivation chain exists in the provided text that could reduce to self-definition or fitted inputs, so the central claims remain independent combinatorial assertions with no detectable circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no information on free parameters, axioms beyond standard graph definitions, or invented entities.

pith-pipeline@v0.9.0 · 5692 in / 985 out tokens · 65402 ms · 2026-05-24T03:07:24.473050+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1. The minimum order of a nonhamiltonian locally linear graph is 12.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 2. The minimum size of a nonhamiltonian locally linear graph of order n is 2n.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.