Automorphism Groups in Extremal Families of Polyhedral Graphs

Bobby Miraftab; Riccardo W. Maffucci

Automorphism Groups in Extremal Families of Polyhedral Graphs

T0 review · 0 major / 6 minor · reviewed 2026-07-30 · grok-4.5

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

Pith's one-line read Minimum-order polyhedra that hit every degree from 3 to n are completely asymmetric for every n at least 14.

desk verdict Clean, checkable asymmetry theorem for min-order degree-universal 3-polytopes, plus several solid Aut classifications; load-bearing chain holds. read the letter →

arxiv 2607.26842 v1 pith:34ZWMVFT submitted 2026-07-29 math.CO

Riccardo W. Maffucci , Bobby Miraftab This is my paper · ORCID

classification math.CO MSC 05C2505C1005C3505C7652B0552B10

keywords AutomorphismgroupPlanargraphPolyhedronDegreesequenceDominatingvertexSelf-dualproduct

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 studies how much symmetry can survive in five extreme families of polyhedral graphs—the wireframe graphs of convex polyhedra. Its central result is that any 3-polytopal graph of smallest possible order that still contains a vertex of every degree from 3 through n is asymmetric: its only automorphism is the identity. The same conclusion holds, by duality, for polyhedra that minimize the number of faces while containing a face of every size 3 through n. Along the way the authors pin down the ordinary and extended automorphism groups of the three polyhedral graphs that remain polyhedral after complementation, classify the possible groups for radius-one polyhedra (especially triangulations), show that self-dual polyhedra unique for their degree sequence have group 1 or C2, and list the groups that arise for polyhedral Cartesian, Kronecker, strong, and lexicographic products. A sympathetic reader cares because these are the graphs forced by extremal counting; the paper shows that the same counting that makes them minimal also kills every nontrivial symmetry.

What carries the argument

The exact planar defect decomposition: for a vertex set X of size at least 3, the quantity 2p+6|X|−16−∑d(x) splits as twice the triangulation defect of G[X] plus the bipartite cut defect of the X–complement edges. On the uniquely high-degree core this defect is forced to 0, 1 or 2, saturating the induced subgraph and fixing every core vertex by degree; Whitney flag rigidity then kills every remaining automorphism.

What would settle it

Exhibit a single 3-polytopal graph on the claimed minimum order p(n) that contains every degree from 3 to n yet admits a nontrivial automorphism, or show that the minimum order itself differs from the ceiling formula used in the defect calculation.

Watch

Extended reading notes

Core claim

For every n≥14, every 3-polytopal graph of minimum order among those containing at least one vertex of each degree 3,4,…,n has trivial automorphism group. Duality yields the same asymmetry for polyhedra that minimize the number of faces while containing an i-gonal face for every 3≤i≤n. The remaining sections give complete group classifications for four other extremal families: complement-polyhedral graphs, radius-one polyhedra, unigraphic self-dual polyhedra, and polyhedral graph products.

Load-bearing premise

The argument leans on a previously established formula for the exact minimum number of vertices needed to realize every degree up to n; if that count is wrong, the defect on the high-degree core no longer vanishes and the uniqueness and saturation steps fail.

Editorial extensions

If this is right

Every minimum-order degree-complete 3-polytope (n≥14) is asymmetric, so no nontrivial rotational or reflection symmetry is possible in that extremal class.
Dually, every face-complete polyhedron of minimum face count is asymmetric.
The three polyhedra with polyhedral complements are never asymmetric; their ordinary groups are C2, C2³ and Dih4, and their extended groups are completely determined.
Radius-one polyhedra can only realize cyclic or dihedral groups (or the five small groups 1, C2, C3, C2×C2, S3 when triangulated).
Unigraphic self-dual polyhedra outside the pyramids have automorphism group exactly 1 or C2 according as the two extreme degrees differ or coincide.

Reading between the lines

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

The same defect-saturation method may force asymmetry in other degree-constrained planar families once a sharp order formula is known.
The open questions on virtually cyclic groups of two-ended planar quasi-transitive graphs suggest the finite classification here is the compact seed of an infinite theory.
Because the high-degree core is pointwise fixed and saturated, these minimal examples are rigid combinatorial building blocks for constructing larger asymmetric polyhedra by controlled attachment.

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 thing worth knowing is Theorem 11: for every n≥14, every minimum-order 3-polytopal graph with all degrees 3 through n is asymmetric, and the dual face version follows. The proof is a short transparent chain—planar defect identity, degree-tail control, saturation of the high-degree core, then Whitney flag rigidity—and it does not lean on extra facial hypotheses.

What is new is mainly Lemma 5 (the exact defect decomposition) and the saturation description of the uniquely high-degree core in Theorem 10. Those force Δ(G[X])≥3 on a pointwise-fixed set, so Aut=1 drops out cleanly. The companion pieces are also usable: ordinary and extended Aut groups for the three polyhedral self-complements (including the nonsplit (C2×C2)⋊C4 for G13), the five-group list for triangulated radius-one polyhedra, the 1-or-C2 dichotomy for the unigraphic self-duals S(m,n), and the product classifications. Edge lists and generator multiplications are explicit enough to check by hand.

Soft spots are real but proportional. The numerical engine is the authors’ prior minimum-order formula (Lemma 2 / [9]); if that order were off, the defect on the core would not sit at 0/1/2 and uniqueness of high degrees would slip. That formula is a published theorem, not a gap inside this manuscript, but the present paper is downstream of it. Self-citation is heavy ([8]–[13]) because the five families are the authors’ own extremal constructions; the new Aut arguments are not circular. Broader significance is modest—tightens enumeration inside a few concrete families rather than resolving a structural open problem.

This is for people who work on polyhedral graphs, degree sequences, and Aut groups of planar 3-connected graphs. A serious referee should see it. I would send it out.

Referee Report

0 major / 6 minor

Summary. The paper determines automorphism groups in five extremal families of polyhedral graphs. The main result (Theorem 11) states that for every n≥14 every minimum-order 3-polytopal graph realizing all vertex degrees 3,…,n is asymmetric; duality yields the analogous statement for minimum-face polyhedra with all face sizes 3,…,n. The argument proceeds from an exact planar defect identity (Lemma 5), degree-tail control (Theorem 7), saturation of the uniquely high-degree core (Theorem 10), and Whitney flag rigidity (Lemmas 3 and 9). The remaining sections compute ordinary and extended automorphism groups of the three polyhedra with polyhedral complements (including Aut±(G13)≅(C2 imes C2)⋄C4), classify Aut groups of radius-one polyhedra (cyclic/dihedral in general; five small groups when triangulated), show that self-dual unigraphs have Aut equal to 1 or C2, and classify Aut groups of polyhedral Cartesian, Kronecker, strong and lexicographic products.

Significance. The asymmetry theorem supplies a clean, checkable instance of forced trivial automorphism groups in an extremal polyhedral family, driven by a reusable defect decomposition rather than ad-hoc facial hypotheses. The explicit edge lists, generator multiplications and nonsplit-extension analysis for the three complement-polyhedral graphs are concrete and verifiable by hand. The radius-one and product classifications round out several concurrent lines of the authors’ work into a coherent picture of restricted Aut groups. The contribution is solid classical graph theory with clear extremal content; the defect identity and core-saturation steps are of independent technical interest.

minor comments (6)

[Section 7] Section 7 (Theorems 23–24) is substantially thinner than Sections 3–5: the arguments largely invoke structural facts from the authors’ arXiv preprints [10,3,12] without restating the needed lemmas. A short self-contained summary of the relevant product classifications (or an explicit pointer to numbered statements) would make the section readable in isolation.
[Section 3 / Lemma 2] Several key inputs ([9, Theorem 2] for the order formula p(n), [8] for the three complement graphs, [13] for the unigraphic self-duals) are the authors’ own prior results. The dependence is legitimate, but a one-sentence reminder in the introduction that Lemma 2 is an external numerical engine (rather than proved here) would help the reader calibrate the logical load.
[Corollary 20, Section 7] Notation for the join versus Cartesian product is occasionally ambiguous (e.g., Pn-2+K2 in Corollary 20 versus □ in Section 7). A brief notational remark at the first occurrence of each product would remove any risk of confusion.
[Theorem 16] In Theorem 16(ii) the presentation of Aut±(G13) is clear, but the claim that the index-two extension is nonsplit is justified only by the absence of involutions in the complementing coset. Adding one sentence that a splitting would require an order-2 complementing element would make the argument fully explicit.
Minor typographic/encoding artefacts appear throughout the extracted text (stray Â, Ê, Ä, Ë characters in titles and author lines; occasional missing spaces in group names such as C 2). These should be cleaned in the production version.
[Section 8] Open Problem 1 asks for the asymptotic proportion of asymmetric polyhedra on p vertices. A pointer to existing enumeration or generation results (e.g., Brinkmann–McKay plantri statistics) would situate the question more sharply.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: asymmetry and Aut classifications are proved from an independent defect/rigidity chain, not by construction from the cited inputs.

full rationale

The load-bearing path for the strongest claim (Theorem 11 / Corollary 12) is: prior minimum-order formula (Lemma 2) → exact planar defect identity (Lemma 5, proved in-text) → high-degree tail and uniqueness (Theorem 7) → core saturation e(X)≥3|X|−7 (Theorem 10) → Δ(G[X])≥3 with X fixed pointwise → flag rigidity (Lemmas 3, 9) → Aut(G)=1. The defect decomposition, facial consequences, and Whitney-flag argument are self-contained and checkable from the manuscript; Aut=1 is not equivalent to p(n) by definition. Other sections (complement graphs, radius-one, unigraphic self-duals, products) either compute Aut groups directly from edge lists/constructions or apply standard structural facts from prior papers as ordinary lemmas. Heavy same-author citation supplies families and numerical inputs but does not make the Aut conclusions true by construction, fitted, or renamed. No self-definitional loop, fitted-as-prediction step, or smuggled ansatz appears.

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

The paper is pure finite graph theory. It rests on classical planar/Euler bounds, Whitney uniqueness for 3-connected planar graphs, and several structural classification theorems from the authors' earlier papers (minimum order, complement-polyhedral triples, product characterizations, unigraphic self-duals). No free parameters are fitted. No new physical or combinatorial entities are postulated beyond ordinary graph-theoretic constructions.

assumptions (7)

standard math Whitney uniqueness: every automorphism of a 3-connected planar graph is determined by the image of one flag (v,e,F); an automorphism fixing a facial triangle pointwise is the identity (Lemma 3).
Classical; used as the final rigidity step in Lemma 9 and Theorem 11.
standard math Planar edge bounds: a simple planar graph on h≥3 vertices has ≤3h-6 edges; a simple bipartite planar graph on p≥4 vertices has ≤2p-4 edges (Lemma 5).
Euler-formula consequences; load-bearing for the defect decomposition.
domain assumption Minimum order of a 3-polytopal graph realizing all degrees 3..n is p(n)=⌈(n²-11n+62)/4⌉ for n≥14 (Lemma 2, cited from [9]).
External numerical input that forces DX∈{0,1,2} on the high-degree core; if false, Theorems 7 and 10 collapse.
domain assumption Exactly three polyhedral graphs have polyhedral complements; they are the self-complementary graphs g14.8.12, g14.8.13, g14.8.39 of degree sequence 4^4 3^4 (Lemma 4, cited from [8]).
Scopes Section 4; Aut computations are conditional on this classification.
domain assumption A polyhedron of radius one on ≥6 vertices has either a unique dominating vertex or is isomorphic to P_{n-2}+K_2 ([11, Lemma 4.1]).
Splits the radius-one case analysis in Section 5.
domain assumption Apart from pyramids, the only self-dual polyhedra unigraphic among self-duals are the graphs S(m,n), m≥n≥4 ([13]).
Scopes Theorem 22.
domain assumption Polyhedral graphs are finite simple 3-connected planar graphs (Steinitz/Whitney setting).
Standing definition used throughout.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Automorphism Groups in Extremal Families of Polyhedral Graphs." pith.science (2026). https://pith.science/paper/34ZWMVFT

@misc{pith2026260726842,
  author       = {Pith},
  title        = {Pith review of: Automorphism Groups in Extremal Families of Polyhedral Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/34ZWMVFT}},
  note         = {Machine review of arXiv:2607.26842}
}

abstract

We study automorphism groups in five extremal families of polyhedral graphs. For every $n\ge14$, we prove that every minimum-order $3$-polytopal graph containing a vertex of each degree $3,4,\ldots,n$ is asymmetric. The proof uses an exact planar defect decomposition, a complete description of the high-degree tail, and a saturation theorem for the subgraph induced by the uniquely high-degree vertices. Duality gives the corresponding asymmetry result for minimum-face polyhedra containing faces of every size $3,4,\ldots,n$. For the three polyhedral graphs whose complements are also polyhedral, we determine the ordinary and extended automorphism groups and identify the extended group \[ \mathsf{Aut}^{\pm}(G_{13})\cong (C_2\times C_2)\rtimes C_4. \] Next, we classify automorphism groups of radius-one polyhedra. In the unique-dominating-vertex case they are cyclic or dihedral, and in the triangulated case the possibilities are \[ 1,\qquad C_2,\qquad C_3,\qquad C_2\times C_2,\qquad S_3. \] For polyhedra that are unigraphic among the class of self-dual, we show that their automorphism group is either $1$ or $C_2$. Finally, we consider polyhedra that are products of graphs, for each of the four standard graph products, and we classify them according to their automorphism group.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 5 canonical work pages

[9]

Maffucci

Riccardo W. Maffucci. Constructing certain families of 3-polytopal graphs.Journal of Graph Theory, 102:484–501, 2023.doi:10.1002/jgt.22882

work page doi:10.1002/jgt.22882 2023
[8]

Maffucci

Riccardo W. Maffucci. On polyhedral graphs and their complements.Aequationes Mathematicae, 96:939–953, 2022.doi:10.1007/s00010-022-00902-5

work page doi:10.1007/s00010-022-00902-5 2022
[13]

On self-duality and unigraphicity for 3-polytopes.Discrete Applied Mathematics, 381:246–260, 2026

Riccardo W Maffucci. On self-duality and unigraphicity for 3-polytopes.Discrete Applied Mathematics, 381:246–260, 2026

2026
[1]

On sums of valencies in planar graphs.Canadian Mathematical Bul- letin, 9(1):111–114, 1966.doi:10.4153/CMB-1966-016-x

Robert Bowen. On sums of valencies in planar graphs.Canadian Mathematical Bul- letin, 9(1):111–114, 1966.doi:10.4153/CMB-1966-016-x

work page doi:10.4153/cmb-1966-016-x 1966
[2]

Planarity of graphs with given degrees of vertices.Nieuw Archief voor Wiskunde, 17:47–60, 1969

Vašek Chvátal. Planarity of graphs with given degrees of vertices.Nieuw Archief voor Wiskunde, 17:47–60, 1969

1969
[3]

Cancellation and regularity for planar, 3-connected Kronecker products.arXiv:2411.13473, 2024

Ruben De March and Riccardo W Maffucci. Cancellation and regularity for planar, 3-connected Kronecker products.arXiv:2411.13473, 2024

arXiv 2024
[4]

M. J. Dunwoody. Planar graphs and covers. 2007.doi:10.48550/arXiv.0708.0920. ArXiv:0708.0920, revised 2009,0708.0920

arXiv doi:10.48550/arxiv.0708.0920 2007
[5]

A note on the structure of locally finite planar quasi-transitive graphs

Ugo Giocanti. A note on the structure of locally finite planar quasi-transitive graphs. The Electronic Journal of Combinatorics, 32(3):P3.50, 2025.doi:10.37236/13751

work page doi:10.37236/13751 2025

Show all 17 references

[6]

Handbook of product graphs

Richard Hammack, Wilfried Imrich, and Sandi Klavar. Handbook of product graphs. 2016

2016
[7]

Jordan-like characterization of auto- morphism groups of planar graphs.Journal of Combinatorial Theory, Series B, 157:1– 39, 2022.doi:10.1016/j.jctb.2022.05.002

Pavel Klavík, Roman Nedela, and Peter Zeman. Jordan-like characterization of auto- morphism groups of planar graphs.Journal of Combinatorial Theory, Series B, 157:1– 39, 2022.doi:10.1016/j.jctb.2022.05.002. 15

2022 doi
[10]

Classification and construction of planar, 3-connected Kro- necker products.arXiv:2402.01407, 2024

Riccardo W Maffucci. Classification and construction of planar, 3-connected Kro- necker products.arXiv:2402.01407, 2024

2024 arXiv
[11]

Classification of polyhedral graphs by numbers of common neighbours.arXiv:2508.01349, 2025

Riccardo W Maffucci. Classification of polyhedral graphs by numbers of common neighbours.arXiv:2508.01349, 2025

2025 arXiv
[12]

Regularity and separation for Sierpiński products of graphs

Riccardo W Maffucci. Regularity and separation for Sierpiński products of graphs. arXiv:2506.16864, 2025

2025 arXiv
[14]

Two-ended quasi-transitive graphs.Dis- crete Mathematics, Algorithms and Applications, 14(7):2250023, 2022.doi:10.1142/ S1793830922500239

Babak Miraftab and Tim Rühmann. Two-ended quasi-transitive graphs.Dis- crete Mathematics, Algorithms and Applications, 14(7):2250023, 2022.doi:10.1142/ S1793830922500239

2022
[15]

Splitting groups with cubic Cayley graphs of connectivity two.Algebraic Combinatorics, 4(6):971–987, 2021.doi:10

Babak Miraftab and Konstantinos Stavropoulos. Splitting groups with cubic Cayley graphs of connectivity two.Algebraic Combinatorics, 4(6):971–987, 2021.doi:10. 5802/alco.188

2021
[16]

Vorlesungen über die Theorie der Polyeder

E Steinitz and H Rademacher. Vorlesungen über die Theorie der Polyeder. 1934

1934
[17]

Congruent graphs and the connectivity of graphs.American Journal of Mathematics, 54(1):150–168, 1932

Hassler Whitney. Congruent graphs and the connectivity of graphs.American Journal of Mathematics, 54(1):150–168, 1932. 16

1932

Pith tools

Reviewed July 30, 2026 · model on record in the stance chip above.

[1] [9]

Maffucci

Riccardo W. Maffucci. Constructing certain families of 3-polytopal graphs.Journal of Graph Theory, 102:484–501, 2023.doi:10.1002/jgt.22882

work page doi:10.1002/jgt.22882 2023

[2] [8]

Maffucci

Riccardo W. Maffucci. On polyhedral graphs and their complements.Aequationes Mathematicae, 96:939–953, 2022.doi:10.1007/s00010-022-00902-5

work page doi:10.1007/s00010-022-00902-5 2022

[3] [13]

On self-duality and unigraphicity for 3-polytopes.Discrete Applied Mathematics, 381:246–260, 2026

Riccardo W Maffucci. On self-duality and unigraphicity for 3-polytopes.Discrete Applied Mathematics, 381:246–260, 2026

2026

[4] [1]

On sums of valencies in planar graphs.Canadian Mathematical Bul- letin, 9(1):111–114, 1966.doi:10.4153/CMB-1966-016-x

Robert Bowen. On sums of valencies in planar graphs.Canadian Mathematical Bul- letin, 9(1):111–114, 1966.doi:10.4153/CMB-1966-016-x

work page doi:10.4153/cmb-1966-016-x 1966

[5] [2]

Planarity of graphs with given degrees of vertices.Nieuw Archief voor Wiskunde, 17:47–60, 1969

Vašek Chvátal. Planarity of graphs with given degrees of vertices.Nieuw Archief voor Wiskunde, 17:47–60, 1969

1969

[6] [3]

Cancellation and regularity for planar, 3-connected Kronecker products.arXiv:2411.13473, 2024

Ruben De March and Riccardo W Maffucci. Cancellation and regularity for planar, 3-connected Kronecker products.arXiv:2411.13473, 2024

arXiv 2024

[7] [4]

M. J. Dunwoody. Planar graphs and covers. 2007.doi:10.48550/arXiv.0708.0920. ArXiv:0708.0920, revised 2009,0708.0920

arXiv doi:10.48550/arxiv.0708.0920 2007

[8] [5]

A note on the structure of locally finite planar quasi-transitive graphs

Ugo Giocanti. A note on the structure of locally finite planar quasi-transitive graphs. The Electronic Journal of Combinatorics, 32(3):P3.50, 2025.doi:10.37236/13751

work page doi:10.37236/13751 2025