pith. sign in

arxiv: 2509.26170 · v2 · pith:KUS2IFFKnew · submitted 2025-09-30 · 🧮 math.CO

The existence of unexpected automorphisms in direct product graphs

Xiaomeng Wang , Yan-Li Qin , Binzhou Xia This is my paper

Pith reviewed 2026-05-25 07:45 UTC · model grok-4.3

classification 🧮 math.CO
keywords graph stabilitydirect productunexpected automorphismsgraph pairscycle graphsautomorphism groupsgraph products
0
0 comments X

The pith

A conjecture reduces the stability of any graph pair to the stability of one graph, proved in one direction with full results for cycles.

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

The paper defines a graph pair as unstable when their direct product has automorphisms outside the product of the individual automorphism groups. It proposes a conjecture giving the sharpest possible way to decide pair stability from the known stability of single graphs, where stability of a graph means the pair with K2 is stable. One direction of the conjecture is established, along with partial results on the converse. This determines stability for wide families of pairs and yields complete answers whenever one factor is a cycle.

Core claim

The authors conjecture that the stability of a pair (Γ, Σ) reduces to the stability of Γ or of Σ in the strongest possible sense, prove one implication of this reduction, obtain partial results on the other implication, and thereby classify stability completely for all pairs in which one factor is a cycle.

What carries the argument

The conjecture that reduces pair instability to single-graph instability via the direct product construction.

If this is right

  • Stability of any pair can be read off from the stability tables of individual graphs once the conjecture is fully settled.
  • All pairs involving a cycle factor now have explicit stability status.
  • The reduction supplies a practical test for instability without computing the full automorphism group of the product.
  • Known results on single-graph stability immediately yield new families of stable and unstable pairs.

Where Pith is reading between the lines

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

  • The same reduction technique may apply to other associative graph products such as the Cartesian or strong product.
  • Computational enumeration of small unstable pairs becomes feasible by checking only the single-graph cases.
  • If the full conjecture holds, the set of unstable pairs is completely determined by the set of unstable graphs.

Load-bearing premise

The graphs satisfy the usual conditions making their direct product connected and the automorphism group of the product well-defined in the standard way.

What would settle it

An explicit pair of graphs (Γ, Σ) in which both (Γ, K2) and (Σ, K2) are stable yet Γ × Σ admits an automorphism outside Aut(Γ) × Aut(Σ).

Figures

Figures reproduced from arXiv: 2509.26170 by Binzhou Xia, Xiaomeng Wang, Yan-Li Qin.

Figure 1
Figure 1. Figure 1: The graph Π U0 U1 W0 W1 If Γ admits an automorphism swapping U and W, then (4) implies that X = Z2 ≀ Z2, and Y = X{U0,W0} is generated by the involution swapping U0 and W0 as well as swapping U1 and W1. In this case, |X : Y | = |X : Y | = 4, and so |X| = 4|Y | = 4|TFA(Γ)|, as part (a) states. Now assume that Γ admits no automorphism swapping U and W. Then Aut(Π+) stabilizes both U0 and W1, while Aut(Π−) st… view at source ↗
read the original abstract

A pair of graphs $(\Gamma,\Sigma)$ is called unstable if their direct product $\Gamma\times\Sigma$ admits automorphisms not from $\mathrm{Aut}(\Gamma)\times\mathrm{Aut}(\Sigma)$, and such automorphisms are said to be unexpected. The stability of a graph $\Gamma$ refers to that of $(\Gamma,K_2)$. While the stability of individual graphs has been relatively well studied, much less is known for graph pairs. In this paper, we propose a conjecture that provides the best possible reduction of the stability of a graph pair to the stability of a single graph. We prove one direction of this conjecture and establish partial results for the converse. This enables the determination of the stability of a broad class of graph pairs, with complete results when one factor is a cycle.

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 paper defines unstable graph pairs (Γ, Σ) via the existence of unexpected automorphisms in the direct product Γ × Σ that lie outside Aut(Γ) × Aut(Σ). Stability of a single graph Γ is the special case of the pair (Γ, K₂). The authors state a conjecture that reduces pair stability to single-graph stability in an optimal manner, prove one direction of the conjecture in full, establish partial results toward the converse, and obtain complete results when one factor is a cycle.

Significance. If the conjecture holds, the reduction would allow stability questions for many pairs to be settled by appealing to the better-understood single-graph case, immediately yielding a broad class of determinations and a complete classification whenever one factor is a cycle. The one-sided proof supplies a concrete, usable tool even before the converse is settled.

minor comments (2)
  1. [Section 2 (Conjecture statement)] The conjecture is presented as providing the 'best possible' reduction, yet the manuscript does not explicitly discuss why no strictly stronger reduction is expected; a short paragraph clarifying the optimality claim would strengthen the motivation.
  2. [Introduction] The implicit standing assumptions on connectedness of the direct product (or the extension of the stability definition to disconnected graphs) are mentioned only in passing; a brief, self-contained reminder in the introduction would aid readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation of minor revision. The referee's summary accurately captures our conjecture reducing pair stability to single-graph stability, the one-sided proof, partial converse results, and the complete classification when one factor is a cycle. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper states a conjecture reducing pair-stability to single-graph stability, proves one direction outright, gives partial results on the converse, and classifies the cycle case completely. No equations, fitted parameters, or predictions appear; the argument consists of a conjecture plus direct proofs that do not reduce by construction to their own inputs or to self-citations. The work is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard definitions of direct product, automorphism group, and stability from prior graph theory; no free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)
  • standard math Direct product of graphs is associative and its automorphism group contains the product of the factors' automorphism groups.
    Invoked implicitly when defining unexpected automorphisms and stability.

pith-pipeline@v0.9.0 · 5658 in / 1239 out tokens · 41584 ms · 2026-05-25T07:45:18.662712+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

18 extracted references · 18 canonical work pages

  1. [1]

    Dobson, ˇS

    T. Dobson, ˇS. Miklaviˇ c and P. ˇSparl, On automorphism groups of deleted wreath products, Mediterr. J. Math., 16 (2019), no. 6, 27 pp

    work page 2019

  2. [2]

    Fernandez and A

    B. Fernandez and A. Hujdurovi´ c, Canonical double covers of circulants,J. Combin. Theory Ser. B, 154 (2022), 49–59

    work page 2022

  3. [3]

    Y. Gan, W. Liu and B. Xia, Unexpected automorphisms in direct product graphs,J. Combin. Theory Ser. B, 171 (2025) 140–164

    work page 2025

  4. [4]

    Hammack, W

    R. Hammack, W. Imrich and S. Klavˇ zar,Handbook of Product Graphs, 2nd ed., CRC Press 2011

    work page 2011

  5. [5]

    Hujdurovi´ c, D

    A. Hujdurovi´ c, D. Mitrovi´ c and D. W. Morris, On automorphisms of the double cover of a circulant graph,Electronic J. Combin., 28 (2021), no. 2, P4.43

    work page 2021

  6. [6]

    Lauri, R

    J. Lauri, R. Mizzi and R. Scapellato, Unstable graphs: a fresh outlook via TF-automorphisms,Ars Math. Contemp., 8 (2015) 115–131

    work page 2015

  7. [7]

    Maruˇ siˇ c, R

    D. Maruˇ siˇ c, R. Scapellato and N. Zagaglia Salvi, A characterization of particular symmetric (0,1) matri- ces,Linear Algebra Appl., 119 (1989), 153–162

    work page 1989

  8. [8]

    Maruˇ siˇ c, R

    D. Maruˇ siˇ c, R. Scapellato and N. Zagaglia Salvi, Generalized Cayley graphs,Discrete Math., 102 (1992), 279–285

    work page 1992

  9. [9]

    D. W. Morris, On automorphisms of direct products of Cayley graphs on abelian groups,Electronic J. Combin., 28 (2021), no. 3, P3.5

    work page 2021

  10. [10]

    Nedela and M

    R. Nedela and M. ˇSkoviera, Regular embeddings of canonical double coverings of graphs,J. Combin. The- ory Ser. B, 67 (1996), 249–277

    work page 1996

  11. [11]

    Y-L. Qin, B. Xia and S. Zhou, Stability of circulant graphs,J. Combin. Theory Ser. B, 136 (2019), 154–169

    work page 2019

  12. [12]

    Y-L. Qin, B. Xia and S. Zhou, Canonical double covers of generalized Petersen graphs, and double generalized Petersen graphs,J. Graph Theory, 97 (2021), 70–81

    work page 2021

  13. [13]

    Y-L. Qin, B. Xia and S. Zhou, Stability of graph pairs involving vertex-transitive graphs,Discrete Math., 347 (2024), no. 4, Paper No. 113856, 6 pp

    work page 2024

  14. [14]

    Y.-L. Qin, B. Xia, J.-X. Zhou and S. Zhou, Stability of graph pairs,J. Combin. Theory Ser. B, 147 (2021) 71–95

    work page 2021

  15. [15]

    Surowski, Stability of arc-transitive graphs,J

    D. Surowski, Stability of arc-transitive graphs,J. Graph Theory, 38 (2001), 95–110

    work page 2001

  16. [16]

    Surowski, Automorphism groups of certain unstable graphs,Math

    D. Surowski, Automorphism groups of certain unstable graphs,Math. Slovaca, 53 (2003), 215–232

    work page 2003

  17. [17]

    Wang, S.-J

    X. Wang, S.-J. Xu and S. Zhou, Stability of graph pairs involving cycles,Graphs Combin., 41 (2025) no. 2, Paper No. 49, 22 pp

    work page 2025

  18. [18]

    Wilson, Unexpected symmetries in unstable graphs,J

    S. Wilson, Unexpected symmetries in unstable graphs,J. Combin. Theory Ser. B, 98 (2008), 359–383. School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu 730000, P. R. China Email address:wangxiaomeng@lzu.edu.cn School of Statistics, Capital University of Economics and Business, Beijing, 100070, P.R. China Email address:ylqin@cueb.edu.cn ...

    work page 2008