Pith. sign in

REVIEW 3 minor 25 references

A connected digraph is unstable exactly when it meets a new necessary and sufficient automorphism condition in its product with K2.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.3

2026-06-26 08:27 UTC pith:VGM6ENMT

load-bearing objection The paper gives the first necessary and sufficient condition for instability of a connected digraph under direct product with K2, plus four sufficient conditions for circulants and two nonexistence results.

arxiv 2606.22947 v1 pith:VGM6ENMT submitted 2026-06-22 math.CO math.GR

On the automorphism group of direct product of digraphs

Guang Rao , Yu Wang , Binzhou Xia This is my paper
classification math.CO math.GR
keywords automorphism groupdirect productdigraph stabilitycirculant digrapharc-transitive digraphCayley digraphabelian group
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper seeks to determine when the automorphism group of the direct product of two digraphs equals the direct product of the separate groups. This equality, called stability of the pair, had been studied for undirected graphs but remained open for digraphs. The authors define the stability of a single digraph G via the pair (G, K2) and give a necessary and sufficient condition for a connected digraph to fail this equality. They apply the condition to obtain four sufficient criteria for instability of circulant digraphs. They further show that certain finite classes admit no nontrivial instability at all.

Core claim

We establish a necessary and sufficient condition for a connected digraph to be unstable, and use it to derive four sufficient conditions for circulant digraphs to be unstable. Moreover, we prove the nonexistence of nontrivially unstable finite arc-transitive circulant digraphs and nontrivially unstable Cayley digraphs of abelian groups of odd order.

What carries the argument

The necessary and sufficient condition for instability of a connected digraph under direct product with K2

Load-bearing premise

The digraph must be connected, since the condition and the nonexistence results are stated only in that case.

What would settle it

A connected digraph that is unstable yet fails the stated condition, or a single example of a nontrivially unstable finite arc-transitive circulant digraph.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Four sufficient conditions for circulant digraphs to be unstable follow directly from the main characterization.
  • No finite arc-transitive circulant digraph can be nontrivially unstable.
  • No Cayley digraph of an abelian group of odd order can be nontrivially unstable.

Where Pith is reading between the lines

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

  • The characterization supplies a practical test that can be applied to other families of digraphs to decide stability.
  • Any instability occurring inside the ruled-out classes must be of the trivial type.
  • The directed results open the possibility of comparing stability behavior between directed and undirected versions of the same underlying graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 3 minor

Summary. The paper initiates the study of stability for direct products of digraphs, where a pair (G,H) is stable if Aut(G×H)=Aut(G)×Aut(H). It defines instability of a digraph G via the pair (G,K_2) and proves a necessary and sufficient condition for a connected digraph to be unstable. This condition is then used to obtain four sufficient conditions for instability of circulant digraphs. The paper also establishes two nonexistence theorems: there are no nontrivially unstable finite arc-transitive circulant digraphs, and no nontrivially unstable Cayley digraphs of abelian groups of odd order.

Significance. If the derivations hold, the work provides the first systematic treatment of digraph stability, extending classical results on undirected graphs. The necessary-and-sufficient condition and the two nonexistence results are load-bearing contributions that could serve as tools for classifying automorphism groups of products in the directed setting. The explicit restriction to connected and finite cases is clearly stated and strengthens the claims.

minor comments (3)
  1. [Abstract and §1] The abstract and introduction should explicitly reference the prior graph-theoretic literature (e.g., Sabidussi) when defining stability to make the extension to digraphs clearer.
  2. [§2] Notation for the direct product operation and the action of automorphisms on directed edges should be introduced with a short example in §2 to aid readers unfamiliar with the directed case.
  3. [§4] The four sufficient conditions for circulant digraphs would benefit from a summary table listing the precise hypotheses on the connection set.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and for recommending minor revision. The referee's summary accurately captures the paper's contributions on the stability of direct products of digraphs. No major comments were raised.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives a necessary-and-sufficient condition for instability of connected digraphs (via the pair (G, K_2)) and related sufficient conditions plus nonexistence results for circulants and Cayley digraphs using standard definitions of direct products, automorphism groups, and arc-transitivity. These are established via graph-theoretic arguments from external literature (e.g., Sabidussi) without any reduction of the central claims to fitted parameters, self-referential definitions, or load-bearing self-citations. All statements are explicitly restricted to the connected/finite setting, and the derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions and results from graph theory and group theory; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard definitions of the direct product of digraphs and of the automorphism group of a digraph, as established in prior literature since Sabidussi.
    The stability notion and all results are built directly on these background definitions.

pith-pipeline@v0.9.1-grok · 5728 in / 1325 out tokens · 28302 ms · 2026-06-26T08:27:09.511013+00:00 · methodology

0 comments
read the original abstract

Determining the conditions under which the direct product of graphs $G$ and $H$ satisfies $\mathrm{Aut}(G\times H)=\mathrm{Aut}(G)\times\mathrm{Aut}(H)$ has been a problem of considerable interest since Sabidussi's classic work in the 1950s. We call such a pair $(G,H)$ stable, and unstable otherwise. Although much progress has been made for graph pairs, the general digraph case has remained completely open. In this paper, we initiate the study of the stability of digraph pairs, and then focus on the stability of a single digraph $G$. This is defined as the stability of the pair $(G,K_2)$ and has been studied extensively when $G$ is undirected. We establish a necessary and sufficient condition for a connected digraph to be unstable, and use it to derive four sufficient conditions for circulant digraphs to be unstable. Moreover, we prove the nonexistence of nontrivially unstable finite arc-transitive circulant digraphs and nontrivially unstable Cayley digraphs of abelian groups of odd order.

discussion (0)

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

Reference graph

Works this paper leans on

25 extracted references

  1. [1]

    Broere, W

    I. Broere, W. Imrich, R. Kalinowski, M. Pil´ sniak, Asymmetric colorings of products of graphs and digraphs, Discrete Appl. Math.266 (2019), 56–64

    2019

  2. [2]

    D¨ orfler, Primfaktorzerlegung und Automorphismen des Kardinalproduktes von Graphen,Glasnik Mat

    W. D¨ orfler, Primfaktorzerlegung und Automorphismen des Kardinalproduktes von Graphen,Glasnik Mat. Ser. III, 9(29) (1974), 15–27

    1974

  3. [3]

    D¨ orfler and W

    W. D¨ orfler and W. Imrich, ¨Uber das starke Produkt von endlichen Graphen, ¨Osterreich. Akad. Wiss. Math.- Natur. Kl. S.-B. II, 178 (1970), 247–262

    1970

  4. [4]

    Feigenbaum, Directed Cartesian-product graphs have unique factorizations that can be computed in polyno- mial time,Discrete Appl

    J. Feigenbaum, Directed Cartesian-product graphs have unique factorizations that can be computed in polyno- mial time,Discrete Appl. Math.15 (1986), no. 1, 105–110

    1986

  5. [5]

    Fernandez and A

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

    2022

  6. [6]

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

    2025

  7. [7]

    Hahn, The automorphism group of the wreath product of directed graphs,European J

    G. Hahn, The automorphism group of the wreath product of directed graphs,European J. Combin., 1 (1980), no. 3, 235–241

    1980

  8. [8]

    Hammack, W

    R. Hammack, W. Imrich and S. Klavˇ zar,Handbook of product graphs, Second edition, Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2011

    2011

  9. [9]

    Hujdurovi´ c, D

    A. Hujdurovi´ c, D. Mitrovi´ c and D.W. Morris, On automorphisms of the double cover of a circulant graph, Electron. J. Combin., 28 (2021), no. 4, Paper No. 4.43, 25 pp

    2021

  10. [10]

    Kov´ acs, Classifying arc-transitive circulants,J

    I. Kov´ acs, Classifying arc-transitive circulants,J. Algebraic Combin., 20 (2004), no. 3, 353–358

    2004

  11. [11]

    Lauri, R

    J. Lauri, R. Mizzi and R. Scapellato, Unstable graphs: a fresh outlook via TF-automorphisms,Ars Math. Con- temp., 8 (2015), no. 1, 115—131

    2015

  12. [12]

    C. H. Li, Permutation groups with a cyclic regular subgroup and arc transitive circulants,J. Algebraic Combin., 21 (2005), no. 2, 131–136

    2005

  13. [13]

    C. H. Li, B. Xia and S. Zhou, An explicit characterization of arc-transitive circulants,J. Combin. Theory Ser. B, 150 (2021), 1–16

    2021

  14. [14]

    Maruˇ siˇ c, R

    D. Maruˇ siˇ c, R. Scapellato and N. Zagaglia Salvi, Generalized Cayley graphs,Discrete Math.102 (1992), no. 3, 279–285. ON THE AUTOMORPHISM GROUP OF DIRECT PRODUCT OF DIGRAPHS 15

    1992

  15. [15]

    D. W. Morris, On automorphisms of direct products of Cayley graphs on abelian groups,Electron. J. Combin., 28 (2021), no. 3, Paper No. 3.5, 10 pp

    2021

  16. [16]

    Nedela and M

    R. Nedela and M. ˇSkoviera, Regular embeddings of canonical double coverings of graphs,J. Combin. Theory Ser. B67 (1996), no. 2, 249—277

    1996

  17. [17]

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

    2019

  18. [18]

    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), no. 1, 70-–81

    2021

  19. [19]

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

    2021

  20. [20]

    Sabidussi, Graph multiplication,Math

    G. Sabidussi, Graph multiplication,Math. Z., 72 (1959/60), 446–457

    1959

  21. [21]

    Sabidussi, The composition of graphs,Duke Math

    G. Sabidussi, The composition of graphs,Duke Math. J., 26 (1959), 693–696

    1959

  22. [22]

    Surowski, Stability of arc-transitive graphs,J

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

    2001

  23. [23]

    Surowski, Automorphism groups of certain unstable graphs,Math

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

    2003

  24. [24]

    P. M. Weichsel, The Kronecker product of graphs,Proc. Amer. Math. Soc., 13 (1962) 47–52

    1962

  25. [25]

    Wilson, Unexpected symmetries in unstable graphs,J

    S. Wilson, Unexpected symmetries in unstable graphs,J. Combin. Theory Ser. B, 98 (2008), no. 2, 359—383. (Rao Guang)College of Education Sciences, The Hong Kong University of Science and Technology (Guangzhou), 511453, P.R.China Email address:guangrao@hkust-gz.edu.cn (Yu Wang)Center for Combinatorics and LPMC, Nankai University, Tianjin, 300071, P.R.China...

    2008