The base size of vertex-transitive cubic graphs
Pith reviewed 2026-05-20 09:26 UTC · model grok-4.3
The pith
Finite connected vertex-transitive cubic graphs are either small, split Praeger-Xu, or have two vertices fixed only by the identity automorphism.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We prove that if Γ is a finite connected vertex-transitive cubic graph, then either |VΓ| ≤ 90, or Γ is a split Praeger-Xu graph, or there exist two vertices α and β such that the identity is the only automorphism of Γ fixing both α and β.
What carries the argument
The pointwise stabilizer of a pair of vertices inside the automorphism group viewed as a transitive permutation group on the vertex set.
If this is right
- Outside the listed exceptions the base size of the automorphism group is at most two.
- Any such graph is uniquely determined by the orbit structure on any chosen pair of vertices.
- Algorithms that compute the full automorphism group need only test the joint stabilizer of two vertices for graphs larger than 90 vertices.
- The possible highly symmetric exceptions are confined to one explicit infinite family.
Where Pith is reading between the lines
- The same style of stabilizer analysis might apply to vertex-transitive graphs of higher but fixed degree.
- Explicit enumeration of all connected vertex-transitive cubic graphs up to 90 vertices would now be sufficient to complete a full list of base-size exceptions.
- The result may interact with existing catalogues of arc-transitive or distance-transitive cubic graphs by restricting their possible automorphism groups.
Load-bearing premise
The graphs under consideration are finite, connected, vertex-transitive, and regular of degree three.
What would settle it
A finite connected vertex-transitive cubic graph with more than 90 vertices that is not a split Praeger-Xu graph and for which every pair of vertices is fixed by some nontrivial automorphism.
read the original abstract
We prove that if $\Gamma$ is a finite connected vertex-transitive cubic graph, then either $|V\Gamma| \le 90$, or $\Gamma$ is a split Praeger--Xu graph, or there exist two vertices $\alpha$ and $\beta$ such that the identity is the only automorphism of $\Gamma$ fixing both $\alpha$ and $\beta$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves that if Γ is a finite connected vertex-transitive cubic graph, then either |VΓ| ≤ 90, or Γ is a split Praeger–Xu graph, or there exist two vertices α and β such that the identity is the only automorphism of Γ fixing both α and β.
Significance. If the result holds, it gives a complete determination of base sizes for automorphism groups of cubic vertex-transitive graphs, with the exceptional families and small-order cases explicitly identified. The argument combines an application of the O’Nan–Scott theorem to the transitive action, constraints from cubic valency on stabilizers and suborbits, explicit constructions for the split Praeger–Xu graphs, and direct verification against the known census for graphs of order at most 90. These elements together constitute a self-contained classification.
minor comments (2)
- [§3] §3: the construction of split Praeger–Xu graphs is given via covers; adding a short explicit description of the vertex set and adjacency relation would improve readability for readers unfamiliar with the family.
- [§5] §5: when appealing to the census of cubic vertex-transitive graphs, state the precise reference or database (including version or date) used for the base-size computations.
Simulated Author's Rebuttal
We thank the referee for their positive assessment of the manuscript and for recommending minor revision. The referee's summary accurately reflects the main theorem: for finite connected vertex-transitive cubic graphs, either the order is at most 90, the graph is a split Praeger-Xu graph, or the base size is at most 2. No specific major comments were provided in the report.
Circularity Check
No significant circularity identified
full rationale
The central theorem is established via exhaustive case division on the action of the automorphism group G = Aut(Γ) as a transitive permutation group of degree |VΓ|. The argument invokes the O'Nan-Scott theorem to classify primitive and imprimitive cases, then applies the cubic valency to constrain suborbits and point stabilizers. Graphs of order at most 90 are dispatched by direct reference to the existing census of cubic vertex-transitive graphs together with explicit base-size calculations; the split Praeger-Xu graphs are defined by an explicit standard construction and shown separately to have base size greater than 2. No step defines a quantity in terms of the target conclusion, fits a parameter to a subset of the data and then renames the fit as a prediction, or relies on a load-bearing self-citation whose content reduces to the present result. All invoked external results (O'Nan-Scott, census data) are independent of the paper's fitted values or outputs.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Γ is a finite connected vertex-transitive cubic graph
Lean theorems connected to this paper
-
IndisputableMonolith/Foundation/AbsoluteFloorClosure.leanabsolute_floor_iff_bare_distinguishability unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We prove that if Γ is a finite connected vertex-transitive cubic graph, then either |VΓ| ≤ 90, or Γ is a split Praeger–Xu graph, or there exist two vertices α and β such that the identity is the only automorphism of Γ fixing both α and β.
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.
Reference graph
Works this paper leans on
-
[1]
Asymmetric coloring of locally finite graphs and profinite permutation groups:
Babai, L. Asymmetric coloring of locally finite graphs and profinite permutation groups:. J. Algebra , volume =
-
[2]
Barbieri, Marco and Grazian, Valentina and Spiga, Pablo , TITLE =. Bull. Aust. Math. Soc. , VOLUME =. 2022 , PAGES =
work page 2022
-
[3]
Barbieri, Marco and Grazian, Valentina and Spiga, Pablo , TITLE =. European J. Combin. , VOLUME =. 2025 , PAGES =
work page 2025
-
[4]
On the intersections of. J. Algebra , volume =. 2026 , author =
work page 2026
-
[5]
Burness and Hong Yi Huang , journal =
Timothy C. Burness and Hong Yi Huang , journal =. On the intersections of nilpotent subgroups in simple groups , year =
- [6]
-
[7]
Marston Conder and Roman Nedela , title =. J. Combin. Theory Ser. B , volume =. 2007 , pages =
work page 2007
-
[8]
J. H. Conway and R. T. Curtis and S. P. Norton and R. A. Parker and R. A. Wilson , title =
-
[9]
A class of finite group-amalgams , journal =
D. A class of finite group-amalgams , journal =. 1980 , pages =
work page 1980
-
[10]
A. Gardiner and Cheryl E. Praeger , title =. European J. Combin. , volume =. 1994 , pages =
work page 1994
-
[11]
Gilman, Robert and Gorenstein, Daniel , TITLE =. Trans. Amer. Math. Soc. , VOLUME =. 1975 , PAGES =
work page 1975
- [12]
-
[13]
David Gluck , TITLE =. J. Group Theory , VOLUME =. 2025 , PAGES =
work page 2025
-
[14]
R. Jajcay and Primo. The. Acta Math. Univ. Comenianae , volume =. 2019 , pages =
work page 2019
-
[15]
R. Jajcay and Primo. On the. J. Combin. Theory Ser. B , VOLUME =. 2022 , PAGES =
work page 2022
-
[16]
Martin Liebeck and Jan Saxl , title =. Proc. London Math. Soc. , volume =. 1991 , pages =
work page 1991
-
[17]
V. D. Mazurov and V. I. Zenkov , TITLE =. Algebra Log. , VOLUME =. 1996 , PAGES =
work page 1996
-
[18]
M. J. Morton , title =. J. Aust. Math. Soc. , volume =. 1991 , pages =
work page 1991
-
[19]
On the number of fixed points of automorphisms of vertex-transitive graphs , JOURNAL =
Poto. On the number of fixed points of automorphisms of vertex-transitive graphs , JOURNAL =. 2021 , PAGES =
work page 2021
-
[20]
Tetravalent arc-transitive graphs with unbounded vertex-stabilizers , JOURNAL =
Poto. Tetravalent arc-transitive graphs with unbounded vertex-stabilizers , JOURNAL =. 2011 , PAGES =
work page 2011
-
[21]
Cubic vertex-transitive graphs on up to 1280 vertices , JOURNAL =
Poto. Cubic vertex-transitive graphs on up to 1280 vertices , JOURNAL =. 2013 , PAGES =
work page 2013
-
[22]
Poto. Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs , journal =. 2015 , pages =
work page 2015
-
[23]
On the vertex-stabiliser in arc-transitive digraphs , JOURNAL =
Poto. On the vertex-stabiliser in arc-transitive digraphs , JOURNAL =. 2010 , PAGES =
work page 2010
-
[24]
Cheryl E. Praeger , title =. European J. Combin. , volume =. 1989 , pages =
work page 1989
-
[25]
Cheryl E. Praeger , title =. J. London Math. Soc. , volume =. 1993 , pages =
work page 1993
-
[26]
Cheryl E. Praeger and M. Y. Xu , title =. European J. Combin. , volume =. 1989 , pages =
work page 1989
-
[27]
and Schneider, Csaba , TITLE =
Praeger, Cheryl E. and Schneider, Csaba , TITLE =. 2018 , PAGES =
work page 2018
-
[28]
Ree, Rimhak , TITLE =. Amer. J. Math. , VOLUME =. 1961 , PAGES =
work page 1961
-
[29]
Sabatini, Luca , title =. Bull. London Math. Soc. , volume =
-
[30]
Suzuki, Michio , TITLE =. Ann. of Math. , VOLUME =. 1962 , PAGES =
work page 1962
-
[31]
W. T. Tutte , title =. Math. Proc. Cam. Phil. Soc. , volume =. 1947 , pages =
work page 1947
- [32]
-
[33]
V. I. Zenkov , title =. Fund. Appl. Math. , volume =. 1996 , pages =
work page 1996
-
[34]
Dixon, John D. and Mortimer, Brian , title =. 1996 , publisher =
work page 1996
-
[35]
Permutation group algorithms , series =
Seress,. Permutation group algorithms , series =. 2003 , publisher =
work page 2003
-
[36]
Barbieri, Marco and Grazian, Valentina and Spiga, Pablo , TITLE =. J. Algebraic Combin. , VOLUME =. 2023 , PAGES =
work page 2023
-
[37]
Barry, Michael J. J. , TITLE =. J. Austral. Math. Soc. A , VOLUME =. 1979 , PAGES =
work page 1979
-
[38]
Timothy Burness , title =. J. Algebra , volume =. 2007 , pages =
work page 2007
-
[39]
Conder, Marston and Lorimer, Peter , TITLE =. J. Combin. Theory Ser. B , VOLUME =. 1989 , PAGES =
work page 1989
-
[40]
Franz Lehner and Primo. Bounding the number of vertices fixed by a non-trivial automorphism of an arc-transitive graph , note =
-
[41]
R. Weiss , title =. Math. Proc. Camb. Phil. Soc. , volume =. 1987 , pages =
work page 1987
-
[42]
R. A. Wilson , title =. Finite Simple Groups: Thirty Years of the Atlas and Beyond , series =
-
[43]
Robert Guralnick and Kay Magaard , title =. J. Algebra , volume =. 1998 , pages =
work page 1998
-
[44]
Marston Conder , title =
-
[45]
Algebraic Combinatorics , volume =
Marston Conder and Gabriel Verret , title =. Algebraic Combinatorics , volume =. 2019 , pages =
work page 2019
-
[46]
Trivalent symmetric graphs on up to 768 vertices , journal =
Marston Conder and Peter Dobcs. Trivalent symmetric graphs on up to 768 vertices , journal =. 2002 , pages =
work page 2002
-
[47]
Praeger and Pablo Spiga , title =
Simon Guest and John Morris and Cheryl E. Praeger and Pablo Spiga , title =. Trans. Amer. Math. Soc. , volume =. 2015 , pages =
work page 2015
-
[48]
Peter Kleidman and Martin Liebeck , title =
-
[49]
R. Lawther and M. W. Liebeck and G. M. Seitz , title =. Pacific J. Math. , volume =. 2002 , pages =
work page 2002
-
[50]
Lifting graph automorphisms by voltage assignments , journal =
Aleksander Malni. Lifting graph automorphisms by voltage assignments , journal =. 2000 , pages =
work page 2000
-
[51]
A. Ramos Rivera and Primo. New structural results on tetravalent half-arc-transitive graphs , journal =. 2019 , pages =
work page 2019
- [52]
-
[53]
A. V. Vasil'ev and V. D. Mazurov , title =. Algebra i Logika , volume =. 1994 , pages =
work page 1994
-
[54]
R. A. Wilson and P. Walsh and J. Tripp and I. Suleiman and R. Parker and S. Norton and S. Nickerson and S. Linton and J. Bray and R. Abbott , title =
-
[55]
A list of 4-valent 2-arc-transitive graphs and finite faithful amalgams of index (4,2) , journal =
Primo. A list of 4-valent 2-arc-transitive graphs and finite faithful amalgams of index (4,2) , journal =. 2009 , pages =
work page 2009
-
[56]
Distinguishing graphs of maximum valence 3 , journal =
H. Distinguishing graphs of maximum valence 3 , journal =
-
[57]
Imrich, Wilfried and Lachmann, Thomas and Tucker, Thomas W. and Wiegel, Gundelinde M. , title =. Art Discrete Appl. Math. , volume =
-
[58]
W. T. Tutte , title =. Canadian J. Math. , volume =. 1959 , pages =
work page 1959
-
[59]
Barbieri, Marco and Zozaya, Andoni , title =. 2025 , howpublished =
work page 2025
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.