Pith. sign in

REVIEW 3 minor 25 references

On the automorphism group of direct product of digraphs

T0 review · 0 major / 3 minor · reviewed 2026-06-26 · grok-4.3

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

Pith's one-line read A connected digraph is unstable exactly when it meets a new necessary and sufficient automorphism condition in its product with K2.

desk verdict 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. read the letter →

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

Guang Rao , Yu Wang , Binzhou Xia This is my paper
classification math.COmath.GR
keywords automorphismgroupdirectproductdigraphstabilitycirculantarc-transitiveCayleyabelian
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

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.

What carries the argument

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

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

Extended reading notes

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.

Load-bearing premise

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

Editorial extensions

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.

Reading between the lines

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.
Share X Bluesky LinkedIn Reddit HN

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 · score 0.0 of 10

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.

Assumptions & free parameters 0 free parameters · 1 assumptions · 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.

assumptions (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.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the automorphism group of direct product of digraphs." pith.science (2026). https://pith.science/paper/VGM6ENMT

@misc{pith2026260622947,
  author       = {Pith},
  title        = {Pith review of: On the automorphism group of direct product of digraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VGM6ENMT}},
  note         = {Machine review of arXiv:2606.22947}
}
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 to comment.

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

Show all 25 references
  1. [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

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

  3. [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

  4. [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

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

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

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

  8. [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

  9. [17]

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

    2019

  10. [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

  11. [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

  12. [20]

    Sabidussi, Graph multiplication,Math

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

    1959

  13. [21]

    Sabidussi, The composition of graphs,Duke Math

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

    1959

  14. [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

  15. [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

  16. [24]

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

    1962

  17. [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)...

    2008

Pith tools

Reviewed June 26, 2026 · model on record in the stance chip above.