pith. sign in

arxiv: 2605.18293 · v1 · pith:C6O7JCSFnew · submitted 2026-05-18 · 🧮 math.CO · math.GR

The base size of vertex-transitive cubic graphs

Pith reviewed 2026-05-20 09:26 UTC · model grok-4.3

classification 🧮 math.CO math.GR MSC 05C2520B25
keywords cubic graphsvertex-transitive graphsbase sizeautomorphism groupsPraeger-Xu graphspermutation groupsregular graphs
0
0 comments X

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.

The paper establishes a trichotomy for these graphs: they must have at most 90 vertices, or belong to the split Praeger-Xu family, or admit two vertices whose common stabilizer is trivial. This trichotomy bounds the cases where the automorphism group requires more than two points to be fixed before it becomes the identity. A sympathetic reader cares because the result limits the possible symmetry structures in 3-regular vertex-transitive graphs and reduces the search space for their automorphisms in the generic case. The argument proceeds by examining the transitive action of the automorphism group on the vertex set and using the cubic condition to constrain local neighborhoods and orbit structures.

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

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

  • 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.

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.

Referee Report

0 major / 2 minor

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)
  1. [§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.
  2. [§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

0 responses · 0 unresolved

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

0 steps flagged

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

0 free parameters · 1 axioms · 0 invented entities

The result rests on the standard definition of vertex-transitive cubic graphs and the action of their automorphism groups; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption Γ is a finite connected vertex-transitive cubic graph
    This is the explicit hypothesis of the theorem.

pith-pipeline@v0.9.0 · 5574 in / 1228 out tokens · 53053 ms · 2026-05-20T09:26:38.665441+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

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

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

59 extracted references · 59 canonical work pages

  1. [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. [2]

    Barbieri, Marco and Grazian, Valentina and Spiga, Pablo , TITLE =. Bull. Aust. Math. Soc. , VOLUME =. 2022 , PAGES =

  3. [3]

    European J

    Barbieri, Marco and Grazian, Valentina and Spiga, Pablo , TITLE =. European J. Combin. , VOLUME =. 2025 , PAGES =

  4. [4]

    On the intersections of. J. Algebra , volume =. 2026 , author =

  5. [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. [6]

    Bosma and J

    W. Bosma and J. Cannon and C. Playoust , title =. J. Symb. Comp. , year =

  7. [7]

    Marston Conder and Roman Nedela , title =. J. Combin. Theory Ser. B , volume =. 2007 , pages =

  8. [8]

    J. H. Conway and R. T. Curtis and S. P. Norton and R. A. Parker and R. A. Wilson , title =

  9. [9]

    A class of finite group-amalgams , journal =

    D. A class of finite group-amalgams , journal =. 1980 , pages =

  10. [10]

    Gardiner and Cheryl E

    A. Gardiner and Cheryl E. Praeger , title =. European J. Combin. , volume =. 1994 , pages =

  11. [11]

    Gilman, Robert and Gorenstein, Daniel , TITLE =. Trans. Amer. Math. Soc. , VOLUME =. 1975 , PAGES =

  12. [12]

    Canadian J

    David Gluck , TITLE =. Canadian J. Math. , VOLUME =. 1983 , PAGES =

  13. [13]

    David Gluck , TITLE =. J. Group Theory , VOLUME =. 2025 , PAGES =

  14. [14]

    Jajcay and Primo

    R. Jajcay and Primo. The. Acta Math. Univ. Comenianae , volume =. 2019 , pages =

  15. [15]

    Jajcay and Primo

    R. Jajcay and Primo. On the. J. Combin. Theory Ser. B , VOLUME =. 2022 , PAGES =

  16. [16]

    Martin Liebeck and Jan Saxl , title =. Proc. London Math. Soc. , volume =. 1991 , pages =

  17. [17]

    V. D. Mazurov and V. I. Zenkov , TITLE =. Algebra Log. , VOLUME =. 1996 , PAGES =

  18. [18]

    M. J. Morton , title =. J. Aust. Math. Soc. , volume =. 1991 , pages =

  19. [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 =

  20. [20]

    Tetravalent arc-transitive graphs with unbounded vertex-stabilizers , JOURNAL =

    Poto. Tetravalent arc-transitive graphs with unbounded vertex-stabilizers , JOURNAL =. 2011 , PAGES =

  21. [21]

    Cubic vertex-transitive graphs on up to 1280 vertices , JOURNAL =

    Poto. Cubic vertex-transitive graphs on up to 1280 vertices , JOURNAL =. 2013 , PAGES =

  22. [22]

    Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs , journal =

    Poto. Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs , journal =. 2015 , pages =

  23. [23]

    On the vertex-stabiliser in arc-transitive digraphs , JOURNAL =

    Poto. On the vertex-stabiliser in arc-transitive digraphs , JOURNAL =. 2010 , PAGES =

  24. [24]

    Praeger , title =

    Cheryl E. Praeger , title =. European J. Combin. , volume =. 1989 , pages =

  25. [25]

    Praeger , title =

    Cheryl E. Praeger , title =. J. London Math. Soc. , volume =. 1993 , pages =

  26. [26]

    Praeger and M

    Cheryl E. Praeger and M. Y. Xu , title =. European J. Combin. , volume =. 1989 , pages =

  27. [27]

    and Schneider, Csaba , TITLE =

    Praeger, Cheryl E. and Schneider, Csaba , TITLE =. 2018 , PAGES =

  28. [28]

    Ree, Rimhak , TITLE =. Amer. J. Math. , VOLUME =. 1961 , PAGES =

  29. [29]

    Sabatini, Luca , title =. Bull. London Math. Soc. , volume =

  30. [30]

    Suzuki, Michio , TITLE =. Ann. of Math. , VOLUME =. 1962 , PAGES =

  31. [31]

    W. T. Tutte , title =. Math. Proc. Cam. Phil. Soc. , volume =. 1947 , pages =

  32. [32]

    , TITLE =

    Walter, John H. , TITLE =. Ann. of Math. , VOLUME =. 1969 , PAGES =

  33. [33]

    V. I. Zenkov , title =. Fund. Appl. Math. , volume =. 1996 , pages =

  34. [34]

    and Mortimer, Brian , title =

    Dixon, John D. and Mortimer, Brian , title =. 1996 , publisher =

  35. [35]

    Permutation group algorithms , series =

    Seress,. Permutation group algorithms , series =. 2003 , publisher =

  36. [36]

    Barbieri, Marco and Grazian, Valentina and Spiga, Pablo , TITLE =. J. Algebraic Combin. , VOLUME =. 2023 , PAGES =

  37. [37]

    Barry, Michael J. J. , TITLE =. J. Austral. Math. Soc. A , VOLUME =. 1979 , PAGES =

  38. [38]

    Timothy Burness , title =. J. Algebra , volume =. 2007 , pages =

  39. [39]

    Conder, Marston and Lorimer, Peter , TITLE =. J. Combin. Theory Ser. B , VOLUME =. 1989 , PAGES =

  40. [40]

    Bounding the number of vertices fixed by a non-trivial automorphism of an arc-transitive graph , note =

    Franz Lehner and Primo. Bounding the number of vertices fixed by a non-trivial automorphism of an arc-transitive graph , note =

  41. [41]

    Weiss , title =

    R. Weiss , title =. Math. Proc. Camb. Phil. Soc. , volume =. 1987 , pages =

  42. [42]

    R. A. Wilson , title =. Finite Simple Groups: Thirty Years of the Atlas and Beyond , series =

  43. [43]

    Robert Guralnick and Kay Magaard , title =. J. Algebra , volume =. 1998 , pages =

  44. [44]

    Marston Conder , title =

  45. [45]

    Algebraic Combinatorics , volume =

    Marston Conder and Gabriel Verret , title =. Algebraic Combinatorics , volume =. 2019 , pages =

  46. [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 =

  47. [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 =

  48. [48]

    Peter Kleidman and Martin Liebeck , title =

  49. [49]

    Lawther and M

    R. Lawther and M. W. Liebeck and G. M. Seitz , title =. Pacific J. Math. , volume =. 2002 , pages =

  50. [50]

    Lifting graph automorphisms by voltage assignments , journal =

    Aleksander Malni. Lifting graph automorphisms by voltage assignments , journal =. 2000 , pages =

  51. [51]

    Ramos Rivera and Primo

    A. Ramos Rivera and Primo. New structural results on tetravalent half-arc-transitive graphs , journal =. 2019 , pages =

  52. [52]

    Sims , title =

    Charles C. Sims , title =. Math. Z. , volume =. 1967 , pages =

  53. [53]

    A. V. Vasil'ev and V. D. Mazurov , title =. Algebra i Logika , volume =. 1994 , pages =

  54. [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. [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 =

  56. [56]

    Distinguishing graphs of maximum valence 3 , journal =

    H. Distinguishing graphs of maximum valence 3 , journal =

  57. [57]

    and Wiegel, Gundelinde M

    Imrich, Wilfried and Lachmann, Thomas and Tucker, Thomas W. and Wiegel, Gundelinde M. , title =. Art Discrete Appl. Math. , volume =

  58. [58]

    W. T. Tutte , title =. Canadian J. Math. , volume =. 1959 , pages =

  59. [59]

    2025 , howpublished =

    Barbieri, Marco and Zozaya, Andoni , title =. 2025 , howpublished =