On Hamilton paths in vertex-transitive graphs of order $10p$

Hao Yu; Shaofei Du; Wenjuan Luo

REVIEW 3 major objections 4 minor 30 references

On Hamilton paths in vertex-transitive graphs of order $10p$

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read This paper proves Hamilton cycles exist in every connected graph of order $10p$ arising from the exceptional $\mathrm{PSL}(2,s^m)$ actions, completing the Hamilton path result for order $10p$.

desk verdict New result in order-10p hamiltonicity, but the proof of Lemma 3.2 has a false claim for k=81 that currently invalidates the argument. read the letter →

arxiv 2411.17780 v1 pith:VGEQL4GG submitted 2024-11-26 math.CO

Shaofei Du , Wenjuan Luo , Hao Yu This is my paper · ORCID

classification math.CO MSC 05C2505C45

keywords vertex-transitivegraphHamiltoncyclepathorbitalPSL(2s^m)diagonalequationliftingsemiregularautomorphism

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 that every connected graph of order $10p$ whose automorphism group contains a vertex-transitive subgroup $\mathrm{PSL}(2,s^m)$ with point stabilizer $\mathbb{Z}_s^m\rtimes\mathbb{Z}_{(s^m-1)/10}$ has a Hamilton cycle, where $s^m+1=2p$ and $p$ is prime. These graphs were the only known exceptions to a 2012 theorem that every connected vertex-transitive graph of order $10p$ with $p\ne 7$ has a Hamilton path. The paper constructs the cycle by showing that each basic orbital graph associated with the exceptional action has a Hamilton cycle. If correct, this closes the last gap and gives a complete Hamilton path statement for all connected vertex-transitive graphs of order $10p$ with $p\ne 7$.

What carries the argument

The key machinery is the lifting-cycle technique combined with the semiregular cyclic subgroup $S\cong\mathbb{Z}_{(k+1)/2}$, which partitions the $10p$ vertices into ten orbits. The argument shows that in each basic orbital graph $Y(i)$ the quotient by $S$ is the complete graph on ten vertices and every pair of $S$-orbits is connected by at least two edges; the lifting lemma then converts a Hamilton cycle in the quotient into one in $Y(i)$. To establish the double-edge condition, the paper counts neighborhood intersections and reduces the count to whether the diagonal equations $a^2+cy^{10}=1$ and $\theta b^2+cy^{10}=-1$ have solutions with $y\ne 0$ over $\mathbb{F}_k$. Proposition 2.2 supplies the needed solutions for $k\ge 72$, and the exceptional case $k=61$ is asserted by a computer check.

What would settle it

Recompute the two diagonal equations over $\mathbb{F}_{61}$ for every coefficient $c$ and confirm that each has a solution with $y\ne 0$; the paper claims this for one of the equations and describes the other as completely similar. If any $c$ fails, Lemma 3.2 collapses for $k=61$.

Watch

Extended reading notes

Core claim

Theorem 1.1 states that if $X$ is a connected graph whose automorphism group contains a vertex-transitive subgroup $\mathrm{PSL}(2,s^m)$, where $s$ is prime and the point stabilizer is $\mathbb{Z}_s^m\rtimes\mathbb{Z}_{(s^m-1)/10}$ with $s^m+1=2p$ for a prime $p$, then $X$ contains a Hamilton cycle. The proof works with the basic orbital graphs $Y(i)$ obtained from the five self-paired suborbits of length $k=s^m$. For each $Y(i)$, the cyclic subgroup $S\cong\mathbb{Z}_{(k+1)/2}$ acts semiregularly with ten orbits, and the paper shows that the quotient graph is complete and that every pair of $S$-orbits is joined by at least two edges. Under those conditions, Lemma 2.1 guarantees that a Hamilton cycle in the quotient lifts to a Hamilton cycle in $Y(i)$. The edge-counting condition is reduced to the solubility of diagonal equations $a^2+cy^{10}=1$ and $\theta b^2+cy^{10}=-1$ over $\mathbb{F}_k$; for $k\ge 72$ this follows from the bound in Proposition 2.2, and the remaining case $k=61$ is handled by a computer check. Since any graph in the exceptional class contains one of the $Y(i)$ as a spanning subgraph, the Hamilton cycle transfers to $X$.

Load-bearing premise

For the exceptional field size $k=61$, the proof depends on an unverified computer check that certain diagonal equations have solutions for every coefficient; if that check is wrong, the Hamilton-cycle claim for that case is unsupported.

Editorial extensions

If this is right

Every connected vertex-transitive graph of order $10p$ with $p\ne 7$ has a Hamilton path.
Every basic orbital graph $Y(i)$ for the exceptional $\mathrm{PSL}(2,s^m)$ action contains a Hamilton cycle.
Since any connected graph in the exceptional class contains one of these $Y(i)$ as a spanning subgraph, each such graph contains a Hamilton cycle.
The lifting-cycle argument shows that the quotient on ten $S$-orbits is complete with double edges, so Hamiltonicity of the quotient transfers to the original graph.

Reading between the lines

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

The same reduction to diagonal equations could be applied to other $\mathrm{PSL}(2,k)$ actions with larger point stabilizers, yielding Hamilton cycles for orders beyond $10p$.
A short arithmetic certificate for the $k=61$ case, such as a list of primitive roots and witness solutions, would make the proof fully independent of computer verification.
Since the paper shows the exceptional graphs have Hamilton cycles, the remaining open question for order $10p$ is whether the non-exceptional cases handled by the 2012 path result actually have Hamilton cycles as well.

Share X Bluesky LinkedIn Reddit HN

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

The headline is that this is a genuinely new result with a standard proof strategy, but Claim 2 of Lemma 3.2 is false for k=81, so the proof as written does not go through.

The paper upgrades the 2012 Kutnar–Marušič–Zhang result by showing that the exceptional PSL(2,s^m) coset graphs of order 10p have Hamilton cycles, not just paths, which would give a clean corollary for all connected vertex-transitive graphs of order 10p, p≠7. That is worth having. The strategy is the usual quotient lift: take the semiregular subgroup S of order p, show the ten S-orbits form a complete quotient with enough multiplicity, and lift a cycle. Claim 1, where the edge count reduces to a^2 + c y^10 = 1, is worked out carefully and the diagonal-equation bound is applied correctly, yielding k≥72.

The problem is Claim 2. The text says "completely similar" for the equation θ b^2 + c y^10 = -1, but it is not similar enough. For k=81 (admissible: 3^4+1=82=2·41 and 10|80), take i=j=n=0 so c=-1. In F_81 the equation becomes θ b^2 - y^10 = -1. The 10th powers are exactly F_9^*. For any x ∈ F_9^*, x-1 is a square in F_81 (since F_9^* lies in the square subgroup), so θ b^2 = x-1 forces b^2 to be a nonsquare times a square, hence no solution. The only solutions have b=0 and y^10=1, and all of these give the same vertex αℓ. So d(αS, αℓS)=1, contradicting the universal claim d≥2. This is a concrete numerical counterexample, not just a gap in presentation.

The k=61 Magma check without code or certificate is a lesser issue. The main theorem may still be true: the single edges form a perfect matching, and the quotient's double-edge graph likely still has a Hamilton cycle, so a refined argument could work. But as it stands, Lemma 3.2's proof fails for an admissible parameter family.

This paper is for people working on the hamiltonicity of vertex-transitive graphs. A correct proof would be a useful incremental step. I would send it to reviewers rather than desk-reject: the flaw is specific and probably fixable, and the result is worth debating. Just make sure the "completely similar" step gets proper scrutiny.

Referee Report

3 major / 4 minor

Summary. The paper addresses a remaining exceptional family in the Hamilton path problem for vertex-transitive graphs of order 10p. Building on the 2012 classification by Kutnar, Marušič, and Zhang, the authors prove (Theorem 1.1) that a connected graph admitting a vertex-transitive PSL(2,s^m) action with point stabilizer Z_s^m ⋊ Z_{(s^m-1)/10} contains a Hamilton cycle, yielding the corollary that all connected vertex-transitive graphs of order 10p (p≠7) have Hamilton paths. The proof constructs basic orbital graphs, quotients by a semiregular subgroup S of order (k+1)/2, and uses a lifting lemma. The central Lemma 3.2 reduces the required double-edge condition to solvability of diagonal equations over F_k, treated via a bound of Lidl–Niederreiter and a Magma check for k=61.

Significance. If correct, the result completes the Hamiltonicity question for order 10p, a natural continuation of work on vertex-transitive graphs of order kp and pq. The proof strategy is attractive: the reduction of edge multiplicities to diagonal equations is elegant, and the use of a general finite-field bound is a useful technique. The manuscript is self-contained apart from the Magma check and the cited classification. However, the argument for Lemma 3.2 has a concrete gap: an admissible case (k=81) is not covered, and the k=61 verification is not fully documented. These issues are central, so the present version is not yet acceptable, though the approach is promising.

major comments (3)

[§3, Lemma 3.2, Claim 2 (Eq. (5))] For the admissible value k=81 (s=3, p=41), the assertion d(αS, αℓS) ≥ 2 is false. Taking i=n=j=0, Eq. (5) becomes θb^2 − y^{10} = −1, with y = θ^{−r} and r ranging over Z_8, so x = y^{10} ranges over F_9^*. For x ∈ F_9^* \ {1}, the equation gives b^2 = θ^{−1}(x−1); since x−1 ∈ F_9^* is a square in F_81 while θ^{−1} is a nonsquare, there is no b. For x=1 the only solutions have b=0, and all such solutions give the same vertex αℓ. Hence d(αS, αℓS)=1, contradicting condition (ii) of Lemma 3.2. This invalidates the proof of Lemma 3.2 for an admissible case of Theorem 1.1.
[§3, Lemma 3.2, Claim 2] The sentence 'Completely similar to Case 1' is not a valid substitute for an argument. In Claim 1 the degenerate solutions are y=0, and they are explicitly subtracted; in Claim 2 the degenerate solutions are b=0, which can persist for all admissible y when c is such that cy^{10}=−1. The proof never shows that a solution of Eq. (5) with b≠0 exists, and the lower bound from Proposition 2.2 counts all solutions (b,y), including the b=0 ones. For k=81 and c=−1 all solutions have b=0, as shown above, so the two cases are not 'completely similar'.
[§3, Lemma 3.2, k=61 check] The phrase 'Checking by Magma, Eq(3) has solutions for any c, over F61' is not reproducible: no code, no list of the finitely many c-values, and no certificate is given. Moreover, this check only concerns Eq(3), i.e., Claim 1 (and Claim 3, which reduces to Eq(3)); Claim 2 requires Eq(5) with the different constant −1 and coefficient θ, and no check for Eq(5) over F61 is reported. Since Proposition 2.2 gives no positive lower bound for k=61, Claim 2 for k=61 is unsupported.

minor comments (4)

[Introduction] The Petersen graph is misspelled as 'Peterson graph' in the introduction.
[§3, Proof of Lemma 3.2] The notation 'Y(i)_1(αtn)' for the neighborhood of αtn in Y(i) is undefined; please define it or use standard notation such as N_{Y(i)}(αtn).
[§3, Lemma 3.1(2)] The expression 'S ∼= Z_{k+1/2}' is ambiguous; it should be written as a cyclic group of order (k+1)/2.
[§3, Proof of Lemma 3.2] The sentence 'Then XS has ten vertices' should refer to the quotient graph of Y(i) by S, not to X itself.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof of Theorem 1.1 is self-contained and does not reduce to its inputs.

full rationale

The paper's central derivation (Lemma 3.2 and Theorem 1.1) is self-contained: the problem is reduced to counting solutions of two diagonal equations, Eq. (3) and Eq. (5), and the required lower bounds come from Proposition 2.2 (Lidl-Niederreiter, an external parameter-free theorem), with the single small case k=61 handled by a Magma check. No parameter is fitted to the target Hamilton cycle, no S-orbit distance is assumed equal to the claim, and the 2012 classification [18] is invoked only at the corollary stage, not inside the proof of Theorem 1.1. The self-citations ([7]-[9]) appear only as background on neighboring Hamiltonicity results and are not load-bearing. The terse 'Completely similar' treatment of Claim 2, the absence of a Magma certificate for k=61, and a possible failure of Claim 2 for k=81 are rigor or correctness concerns, not circularity: none of these steps assumes the conclusion or uses the paper's own result as its input. Therefore the derivation chain is free of circularity.

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

No free parameters are fitted and no new entities are introduced. The proof relies on the standard finite-field solution bound, the quotient lifting lemma, a finite Magma check for k=61, and the external 2012 classification when deriving the corollary; the Magma check is the only ad hoc, unverified dependence.

assumptions (4)

standard math Lidl-Niederreiter diagonal equation bound (Proposition 2.2)
Counts solutions to a^2 + c y^10 = 1 and analogues over F_k; the proof relies on it for k≥72.
standard math Lemma 2.1 lifting-cycle lemma
Used to lift a Hamilton cycle from the quotient by S to a Hamilton cycle in Y(i); the proof is only sketched as straightforward.
ad hoc to paper Magma verification for k=61 that Eq(3) has solutions for every relevant c
A finite check asserted without code or certificate; needed for the k=61 case.
standard math Kutnar, Marusic, Zhang classification of order 10p graphs without Hamilton paths (Theorem from [18])
Combined with Theorem 1.1 to obtain Corollary 1.2; the central theorem does not depend on it.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Hamilton paths in vertex-transitive graphs of order $10p$." pith.science (2026). https://pith.science/paper/VGEQL4GG

@misc{pith2026241117780,
  author       = {Pith},
  title        = {Pith review of: On Hamilton paths in vertex-transitive graphs of order $10p$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VGEQL4GG}},
  note         = {Machine review of arXiv:2411.17780}
}

abstract

It was shown by Kutnar, Maru\v si\v c and Zhang in 2012 that every connected vertex-transitive graph of order $10p$, where $p$ is a prime and $p\ne 7$, contains a Hamilton path, except for graphs $X$ arising from the action of PSL$(2, s^m)$ on cosets of $\mathbb{Z}_s^m\rtimes \mathbb{Z}_{\frac{s^m-1}{10}}$, where $s$ is a prime. In this paper, Hamilton cycles of these exceptions $X$ will be found.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 28 canonical work pages

[1]

Alspach, The search for long paths and cycles in vertex-tran sitive graphs and digraphs, in: Kevin L

B. Alspach, The search for long paths and cycles in vertex-tran sitive graphs and digraphs, in: Kevin L. McAvaney (ed.), Combinatorial Mathematics Vlll , Lecture Notes in Mathematics 884, Springer-Verlag, Berlin, 1981, 14–22

work page 1981
[2]

Alspach, Lifting Hamilton cycles of quotient graphs, Discrete Math

B. Alspach, Lifting Hamilton cycles of quotient graphs, Discrete Math. 78 (1989), 25–36

work page 1989
[3]

P. J. Cameron (ed.), Problems from the Fifteenth British Combina torial Con- ference, Discrete Math. 167/168 (1997), 605–615

work page 1997
[4]

P. J. Cameron, M. Giudici, G. A. Jones, W. M. Kantor, M. H. Klin, D. Maruˇ siˇ c, L. A. Nowitz, Transitive permutation groups without semiregular su bgroups, J. London Math. Soc. 66 (2002), 325–333

work page 2002
[5]

Y. Q. Chen, On Hamiltonicity of vertex-transitive graphs and digr aphs of order p4, J. Combin. Theory Ser. B 72 (1998), 110–121

1998
[6]

Curran and J

S. Curran and J. A. Gallian, Hamiltonian cycles and paths in Cayley gr aphs and digraphs - a survey, Discrete Math. 156 (1996), 1–18

work page 1996
[7]

S. F. Du, K. Kutnar and D. Maruˇ siˇ c, Hamilton cycles in primeitive vertex- transitive graphs of a product of two primes—the case PSL(2 , q2) acting on cosets of PSL(2 , q), Ars Math. Contemp. 19 (2020), 1–15. 9

work page 2020
[8]

S. F. Du, K. Kutnar and D. Maruˇ siˇ c, Resolving the Hamiltonian p roblem for vertex-transitive graphs of order a product of two primes, Combinatorica 41 (2021), 507–543

work page 2021

Show all 30 references

[9]

S. F. Du, Y. Tian and H. Yu, Hamilton cycles in primitive graphs of ord er 2 rs, Ars Math. Contemp. 23 (2023), Paper No. 5, 24 pp

2023
[10]

Dobson, A

E. Dobson, A. Malniˇ c, D. Maruˇ siˇ c and L. A. Nowitz, Semireg ular automor- phisms of vertex-transitive graphs of certain valencies, J. Combin. Theory Ser. B 97 (2007), 371–380

2007
[11]

Durnberger, Connected Cayley graphs of semi-direct prod ucts of cyclic groups of prime order by abelian groups are hamiltonian, Discrete Math

E. Durnberger, Connected Cayley graphs of semi-direct prod ucts of cyclic groups of prime order by abelian groups are hamiltonian, Discrete Math. 46 (1983), 55–68

1983
[12]

Ghaderpour and D

E. Ghaderpour and D. Witte Morris, Cayley graphs on nilpotent g roups with cyclic commutator subgroup are hamiltonian, Ars Math. Contemp. 7 (2014), 55–72

2014
[13]

Giudici, Quasiprimitive groups with no ﬁxed point free elements o f prime order, J

M. Giudici, Quasiprimitive groups with no ﬁxed point free elements o f prime order, J. London Math. Soc. 67 (2003), 73–84

2003
[14]

H. H. Glover, K. Kutnar, A. Malniˇ c and D. Maruˇ siˇ c, Hamilton cycles in (2, odd, 3)-Cayley graphs, Proc. London Math. Soc. 104 (2012), 1171–1197

2012
[15]

H. H. Glover and D. Maruˇ siˇ c, Hamiltonicity of cubic Cayley grap h, J. Euro. Math. Soc. 9 (2007), 775–787

2007
[16]

Kutnar and D

K. Kutnar and D. Maruˇ siˇ c, Hamiltonicity of vertex-transitive graphs of order 4p, European J. Combin. 29 (2008), 423–438

2008
[17]

Kutnar and D

K. Kutnar and D. Maruˇ siˇ c, Hamilton cycles and paths in verte x-transitive graphs - Current directions, Discrete Math. 309 (2009), 5491–5500

2009
[18]

Kutnar, D

K. Kutnar, D. Maruˇ siˇ c and C. Zhang, Hamilton paths in verte x-transitive graphs of order 10 p, European J. Combin. 33 (2012), 1043–1077

2012
[19]

Kutnar and P

K. Kutnar and P. ˇSparl, Hamilton paths and cycles in vertex-transitive graphs of order 6 p, Discrete Math. 309 (2009), 5444–5460

2009
[20]

Niederreiter, Finite ﬁelds , Cambridge University Press, Cam- bridge, 1997

R, Lidl and H. Niederreiter, Finite ﬁelds , Cambridge University Press, Cam- bridge, 1997

1997
[21]

Lov´ asz, Combinatorial Structures and Their Applications, ed

L. Lov´ asz, Combinatorial Structures and Their Applications, ed. R.Guy, H.Hanam, N.Sauer and J.Schonheim, Gordon and Breach, New York, 1 970
[22]

Maruˇ siˇ c, On vertex symmetric digraphs,Discrete Math

D. Maruˇ siˇ c, On vertex symmetric digraphs,Discrete Math. 36 (1981), 69–81

1981
[23]

Maruˇ siˇ c, Hamiltonian circuits in Cayley graphs, Discrete Math

D. Maruˇ siˇ c, Hamiltonian circuits in Cayley graphs, Discrete Math. 46 (1983), 49–54. 10

1983
[24]

Maruˇ siˇ c, Vertex transitive graphs and digraphs of order pk, Cycles in graphs (Burnaby, B.C., 1982) 115–128, Ann

D. Maruˇ siˇ c, Vertex transitive graphs and digraphs of order pk, Cycles in graphs (Burnaby, B.C., 1982) 115–128, Ann. Discrete Math. 27, North-Holland, Am- sterdam, 1985

1982
[25]

Maruˇ siˇ c, Hamiltonian cycles in vertex symmetric graphs of order 2 p2, Dis- crete Math

D. Maruˇ siˇ c, Hamiltonian cycles in vertex symmetric graphs of order 2 p2, Dis- crete Math. 66 (1987), 169–174

1987
[26]

Maruˇ siˇ c and T

D. Maruˇ siˇ c and T. D. Parsons, Hamiltonian paths in vertex-symmetric graphs of order 5 p, Discrete Math. 42 (1982), 227–242

1982
[27]

Maruˇ siˇ c and T

D. Maruˇ siˇ c and T. D. Parsons, Hamiltonian paths in vertex-symmetric graphs of order 4 p, Discrete Math. 43 (1983), 91–96

1983
[28]

Witte Morris, Odd-order Cayley graphs with commutator sub group of order pq are hamiltonian, Ars Math

D. Witte Morris, Odd-order Cayley graphs with commutator sub group of order pq are hamiltonian, Ars Math. Contemp. 8 (2015), 1–28

2015
[29]

Witte Morris, Cayley graphs on groups with commutator subg roup of order 2p are hamiltonian, The Art of Discrete and Applied Math

D. Witte Morris, Cayley graphs on groups with commutator subg roup of order 2p are hamiltonian, The Art of Discrete and Applied Math. 1 (2018), #P1.04

2018
[30]

J. Y. Zhang, Vertex-transitive digraphs of order p5 are Hamiltonian, Electronic J. Combin. 22 (2015), #P1.76. 11

2015

Pith tools

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

[1] [1]

Alspach, The search for long paths and cycles in vertex-tran sitive graphs and digraphs, in: Kevin L

B. Alspach, The search for long paths and cycles in vertex-tran sitive graphs and digraphs, in: Kevin L. McAvaney (ed.), Combinatorial Mathematics Vlll , Lecture Notes in Mathematics 884, Springer-Verlag, Berlin, 1981, 14–22

work page 1981

[2] [2]

Alspach, Lifting Hamilton cycles of quotient graphs, Discrete Math

B. Alspach, Lifting Hamilton cycles of quotient graphs, Discrete Math. 78 (1989), 25–36

work page 1989

[3] [3]

P. J. Cameron (ed.), Problems from the Fifteenth British Combina torial Con- ference, Discrete Math. 167/168 (1997), 605–615

work page 1997

[4] [4]

P. J. Cameron, M. Giudici, G. A. Jones, W. M. Kantor, M. H. Klin, D. Maruˇ siˇ c, L. A. Nowitz, Transitive permutation groups without semiregular su bgroups, J. London Math. Soc. 66 (2002), 325–333

work page 2002

[5] [5]

Y. Q. Chen, On Hamiltonicity of vertex-transitive graphs and digr aphs of order p4, J. Combin. Theory Ser. B 72 (1998), 110–121

1998

[6] [6]

Curran and J

S. Curran and J. A. Gallian, Hamiltonian cycles and paths in Cayley gr aphs and digraphs - a survey, Discrete Math. 156 (1996), 1–18

work page 1996

[7] [7]

S. F. Du, K. Kutnar and D. Maruˇ siˇ c, Hamilton cycles in primeitive vertex- transitive graphs of a product of two primes—the case PSL(2 , q2) acting on cosets of PSL(2 , q), Ars Math. Contemp. 19 (2020), 1–15. 9

work page 2020

[8] [8]

S. F. Du, K. Kutnar and D. Maruˇ siˇ c, Resolving the Hamiltonian p roblem for vertex-transitive graphs of order a product of two primes, Combinatorica 41 (2021), 507–543

work page 2021