pith. sign in

arxiv: 2507.16301 · v2 · submitted 2025-07-22 · 🧮 math.CO · math.GR

Automorphism groups and Distinguishing Colorings of Central and Middle Graphs

Amitayu Banerjee , Alexa Gopaulsingh , Zal\'an Moln\'ar This is my paper

Pith reviewed 2026-05-19 03:50 UTC · model grok-4.3

classification 🧮 math.CO math.GR
keywords automorphism groupscentral graphsmiddle graphsdistinguishing numberdistinguishing indexsubdivision graphsgraph symmetries
0
0 comments X

The pith

If a graph G has at least four vertices, then Aut(G) is isomorphic to Aut(C(G)) and Aut(M(G)).

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

The paper proves that for any simple connected graph G with at least four vertices, the automorphism groups of G, its central graph C(G), and its middle graph M(G) are all isomorphic as abstract groups. These isomorphisms are then used to establish new upper bounds on the distinguishing number and distinguishing index of C(G) and M(G) by adapting an existing algorithm for computing such parameters. A sympathetic reader would care because distinguishing numbers quantify the fewest labels needed to eliminate all nontrivial symmetries, so relating them across graph constructions gives a method to bound symmetries in modified graphs without recomputing from scratch. The central and middle graphs are built from the subdivision graph S(G) by adding edges between subdivided vertices that correspond to adjacent edges or non-adjacent original vertices.

Core claim

We show that if the order of G is at least 4, then Aut(G), Aut(C(G)), and Aut(M(G)) are isomorphic as abstract groups. We apply these results to obtain new upper bounds of the distinguishing number and the distinguishing index of C(G) and M(G) inspired by an algorithm due to Kalinowski, Pilsniak, and Wozniak from 2016.

What carries the argument

The isomorphism between Aut(G), Aut(C(G)), and Aut(M(G)) induced by the constructions of the central graph and middle graph from the subdivision graph S(G).

If this is right

  • The distinguishing number of C(G) satisfies the same upper bounds that the 2016 algorithm yields for G itself.
  • The distinguishing index of M(G) inherits upper bounds directly from those established for the automorphism group of G.
  • Any distinguishing coloring of G induces corresponding colorings on C(G) and M(G) via the group isomorphism.
  • The results extend the reach of existing distinguishing algorithms to the classes of central graphs and middle graphs without additional symmetry-breaking cost.

Where Pith is reading between the lines

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

  • The group preservation may mean that other symmetry-related parameters, such as the fixing number, behave identically under these two constructions for large enough base graphs.
  • Direct computational checks on all connected graphs of order exactly four would either confirm the isomorphism or reveal the smallest counterexample.
  • Similar isomorphism statements could be tested for other common derived graphs that add edges to a subdivision, such as certain line graphs or total graphs.

Load-bearing premise

The specific edge additions that define C(G) and M(G) from S(G) introduce no automorphisms beyond those already present in G, when G has four or more vertices.

What would settle it

A connected graph G on four vertices together with an explicit automorphism of C(G) or M(G) that moves an original vertex of G to a subdivided vertex and cannot be matched to any automorphism of G.

Figures

Figures reproduced from arXiv: 2507.16301 by Alexa Gopaulsingh, Amitayu Banerjee, Zal\'an Moln\'ar.

Figure 1
Figure 1. Figure 1: Graphs L(Q), Q, and C + 6 . Lemma 2.8. If ψ ∈ Aut(G+) such that ψ(u) = u for all u ∈ U1, then ψ = idG+ . Proof. Let ui ∈ U2. If ψ(ui) = uj for some uj ∈ U2\{ui}, then ψ(vi) = vj since the automorphisms preserve adjacency, which is a contradiction to the given assumption. □ Lemma 2.9. If G is a non-trivial connected graph and φ ∈ Aut(G+), then φ(Ui) = Ui for i ∈ {1, 2}. Proof. In G+, each vertex of U1 has a… view at source ↗
Figure 2
Figure 2. Figure 2: Edge colorings of G with 2 colors that are only preserved by idG where G ∈ {C(C4), C(C5), C(K4), C(K5)}. Case (ii): G contains a cycle but G ̸∈ {Cn, Kn}. Thus, we can choose a vertex v0 lying on a cycle such that the sphere S2(v0) is non-empty. Consider a BFS￾spanning tree T of G rooted at v0. For a vertex v ∈ T, we denote Xv,u = ({v, wv,u}, {wv,u, u}) if wv,u ∈ V2 subdivides the edge {v, u} ∈ E(T) and N(v… view at source ↗
Figure 3
Figure 3. Figure 3: A vertex coloring of C(K1,4) with 2 colors and an edge coloring of C(K1,5) with 3 colors that are only preserved by trivial automorphisms. Remark 3.5. For any integer n ≥ 1, we have D′ (C(K1,n)) = D(C(K1,n)) = ⌈ √ n⌉ = ⌈ p ∆(K1,n)⌉. This shows that the bounds mentioned in Theorems 3.2 and 3.4 are sharp (see [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: In the figure above, shaded regions contain vertices belonging to V2. Case (ii): Assume that there exists vi ∈ V1 such that S 1≤t≤r Xkt ⊆ NC(G)(vi) ∩ V2 for some k1, ..., kr ≤ l. Since ∆(G) < n − 2, this implies NC(G)(vi) ∩ V1 ̸= ∅. Let NC(G)(vi) ∩ V1 = {m1, ..., mp} for some positive integer p. For every 1 ≤ j ≤ p, assume that mj ∈ Xtj for some tj ≤ l. If for some 1 ≤ j ≤ p, we have Xtj ∩V1 ⊆ NC(G)(vi), t… view at source ↗
Figure 5
Figure 5. Figure 5: Graph G when n = 6. We note that for any TDC f = (X1, ..., Xl) of C(G), |{Xi : Xi ⊆ V1, |Xi | = 1}| ≥ n−2. Otherwise, the following cases can occur. Case (i): There exist two color classes of two elements, say X1 = {vi , vj} and X2 = {vk, vt}. Observe that both vi ∈ NC(G)(vk) ∩ NC(G)(vt) and vj ∈ NC(G)(vk) ∩ NC(G)(vt) can’t happen together by the definition of G, since n ≥ 5. Without loss of generality, as… view at source ↗
read the original abstract

Let G be a simple, finite, connected, and undirected graph. The middle graph M(G) of G is obtained from the subdivision graph S(G) after joining pairs of subdivided vertices that lie on adjacent edges of G and the central graph C(G) of G is obtained from S(G) after joining all non-adjacent vertices of G. We show that if the order of G is at least 4, then Aut(G), Aut(C(G)), and Aut(M(G)) are isomorphic (as abstract groups) and apply these results to obtain new upper bounds of the distinguishing number and the distinguishing index of C(G) and M(G) inspired by an algorithm due to Kalinowski, Pilsniak, and Wozniak from 2016.

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

2 major / 2 minor

Summary. The paper claims that for any connected simple undirected graph G with |V(G)| ≥ 4, the groups Aut(G), Aut(C(G)), and Aut(M(G)) are isomorphic as abstract groups. It then applies these isomorphisms to derive new upper bounds on the distinguishing number D and distinguishing index D' of C(G) and M(G), drawing on the 2016 algorithm of Kalinowski, Pilśniak, and Woźniak.

Significance. If the isomorphisms are established rigorously, the result provides a uniform way to relate the symmetry groups of G to those of its central and middle graphs, which in turn yields concrete, transferable bounds on distinguishing colorings. This extends the literature on automorphism-preserving graph constructions and distinguishing parameters for derived graphs.

major comments (2)
  1. [Section 3 (isomorphism for middle graphs)] The proof that Aut(M(G)) ≅ Aut(G) must supply a uniform, non-degree argument that the original-vertex set O is preserved by every automorphism of M(G). The degree-based separation used for C(G) (original vertices have degree n−1) does not carry over, since deg_M(v) for v ∈ O equals the original degree while deg_M(e) for e ∈ E equals deg(u)+deg(v), and these ranges overlap for many graphs (e.g., any G containing both a degree-4 vertex and an edge whose endpoints sum to 4). Without an invariant that works for arbitrary degree sequences, it is possible that some automorphisms mix O and E, making |Aut(M(G))| strictly larger than |Aut(G)|.
  2. [Theorem 3.2 and its proof] The manuscript states the isomorphism for all connected G with n ≥ 4 but provides no explicit case-by-case verification or additional structural invariant (e.g., adjacency to the subdivided edges or parity arguments) that rules out mixing when degrees coincide. This is load-bearing for both the group-isomorphism claim and the subsequent distinguishing-number bounds that inherit the group order.
minor comments (2)
  1. [Abstract] The abstract refers to “new upper bounds” without indicating whether they improve on known bounds for the same graphs or merely transfer existing bounds from G; a short comparative sentence would clarify the contribution.
  2. [Section 2 (definitions)] Notation for the partition of V(M(G)) into original vertices and subdivision vertices is introduced but not used uniformly in later sections; consistent symbols (e.g., O and E) would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and for identifying a potential weakness in the presentation of the isomorphism for middle graphs. We address the major comments point by point below. We agree that the current argument requires strengthening and will revise the manuscript to supply a uniform structural invariant.

read point-by-point responses

  1. Referee: [Section 3 (isomorphism for middle graphs)] The proof that Aut(M(G)) ≅ Aut(G) must supply a uniform, non-degree argument that the original-vertex set O is preserved by every automorphism of M(G). The degree-based separation used for C(G) (original vertices have degree n−1) does not carry over, since deg_M(v) for v ∈ O equals the original degree while deg_M(e) for e ∈ E equals deg(u)+deg(v), and these ranges overlap for many graphs (e.g., any G containing both a degree-4 vertex and an edge whose endpoints sum to 4). Without an invariant that works for arbitrary degree sequences, it is possible that some automorphisms mix O and E, making |Aut(M(G))| strictly larger than |Aut(G)|.

    Authors: We agree that a purely degree-based separation is insufficient for middle graphs when degree sequences permit overlaps, and the manuscript's current presentation does not explicitly rule out mixing in such cases. We will revise Section 3 to include a uniform structural argument: the set O consists exactly of the vertices whose entire neighborhood lies in the independent-set complement of the clique cover formed by the edge-vertex adjacencies. More precisely, we will prove that any automorphism must map O to O by showing that vertices in O are the unique vertices that are non-adjacent to all other vertices in their closed neighborhood except through the subdivided structure, combined with the fact that the induced subgraph on the image of O must reproduce the original adjacency via the incident edge-vertices. This invariant holds independently of specific degree values and will be stated and proved in full detail. revision: yes

  2. Referee: [Theorem 3.2 and its proof] The manuscript states the isomorphism for all connected G with n ≥ 4 but provides no explicit case-by-case verification or additional structural invariant (e.g., adjacency to the subdivided edges or parity arguments) that rules out mixing when degrees coincide. This is load-bearing for both the group-isomorphism claim and the subsequent distinguishing-number bounds that inherit the group order.

    Authors: We acknowledge that the proof of Theorem 3.2 currently lacks an explicit additional invariant or case analysis for degree-coincidence situations. We will expand the proof to incorporate the structural characterization described above, which serves as the required uniform invariant. No case-by-case verification on degree sequences will be needed once the invariant is established, but we will add a short remark confirming that the argument covers all connected graphs with n ≥ 4. The revised proof will directly support the subsequent bounds on D and D'. revision: yes

Circularity Check

0 steps flagged

No significant circularity; direct structural proof of group isomorphisms

full rationale

The paper establishes Aut(G) ≅ Aut(C(G)) ≅ Aut(M(G)) for connected G with n ≥ 4 via explicit constructions of C(G) and M(G) from the subdivision graph S(G), followed by case analysis showing that any automorphism of the derived graphs must map original vertices to original vertices and subdivision vertices to subdivision vertices while inducing an automorphism of G. This chain relies on degree sequences, adjacency relations, and partition preservation arguments that are verified directly from the definitions rather than reducing to a fitted parameter, self-referential definition, or load-bearing self-citation. The distinguishing-number bounds are presented as straightforward applications of an external 2016 algorithm once the isomorphisms are in hand. No equation or claim in the derivation is equivalent to its own input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof relies on standard definitions of subdivision, central, and middle graphs together with the assumption that G is simple, finite, connected, and undirected. No free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption G is simple, finite, connected, and undirected
    Stated in the first sentence of the abstract; required for the constructions of S(G), C(G), and M(G) to be well-defined.

pith-pipeline@v0.9.0 · 5663 in / 1366 out tokens · 25504 ms · 2026-05-19T03:50:21.418463+00:00 · methodology

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

38 extracted references · 38 canonical work pages

  1. [1]

    M. O. Albertson and K. L. Collins, Symmetry Breaking in Graphs, Electron. J. of Combin. 3 (1996)

    work page 1996

  2. [2]

    Alikhani, N

    S. Alikhani, N. Ghanbari, and S. Soltani, Total dominator chromatic number of k-subdivision of graphs, Art Discret. Appl. Math. 6 (2023)

    work page 2023

  3. [3]

    Alikhani and S

    S. Alikhani and S. Soltani, The distinguishing number and the distinguishing index of line and graphoidal graph(s), AKCE Int J Graphs Co. 17 (2020), 1–6. doi: https://doi.org/10.1016/j.akcej.2018.08.006

    work page doi:10.1016/j.akcej.2018.08.006 2020

  4. [4]

    Alikhani and S

    S. Alikhani and S. Soltani, Distinguishing number and distinguishing index of natural and fractional powers of graphs, Bull. Iranian Math. Soc. 43 (2017), no. 7, 2471–2482

    work page 2017

  5. [5]

    Banerjee, A

    A. Banerjee, A. Gopaulsingh, and Z. Moln´ ar: Distinguishing chromatic number of middle and subdivision graphs,Trans. Comb. (to appear), url: https://toc.ui.ac.ir/article_29574.html

    work page

  6. [6]

    Behzad, Graphs and their chromatic number, Ph.D.Thesis, Michigan State University, (1965)

    M. Behzad, Graphs and their chromatic number, Ph.D.Thesis, Michigan State University, (1965)

    work page 1965

  7. [7]

    Chen, On the adjacent vertex distinguishing total coloring numbers of graphs with ∆=3, Discrete Math

    X. Chen, On the adjacent vertex distinguishing total coloring numbers of graphs with ∆=3, Discrete Math. 308 (2008), 4003–4007

    work page 2008

  8. [8]

    Chen and X

    M. Chen and X. Guo, Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes, Information Processing Letters 109 (2009), 599–602

    work page 2009

  9. [9]

    Chen, M.Y

    X.G. Chen, M.Y. Sohn, and Y.F. Wang, Total domination number of central trees, Bull. Korean Math. Soc. 57 (2020), 245–250

    work page 2020

  10. [10]

    E. J. Cockayne, R. M. Dawes, and S. T. Hedetniemi, Total domination in graphs, Networks 10 (1980), 211–219

    work page 1980

  11. [11]

    Effantin, A note on Grundy colorings of central graphs, Australas

    B. Effantin, A note on Grundy colorings of central graphs, Australas. J. Comb. 68 (2017), 346–356

    work page 2017

  12. [12]

    Fujita, F

    S. Fujita, F. Kazemnejad, and B. Pahlavsay, New classification of graphs in view of the domination number of central graphs, arXiv preprint: doi: https://doi.org/10.48550/arXiv.2204.10292

    work page doi:10.48550/arxiv.2204.10292

  13. [13]

    Hamada and I.Yoshimura, Traversability and connectivity of the middle graph of a graph, Discrete Math

    T. Hamada and I.Yoshimura, Traversability and connectivity of the middle graph of a graph, Discrete Math. 14 (1976) no. 3, 247–255. doi:https://doi.org/10.1016/0012-365X(76)90037-6

    work page doi:10.1016/0012-365x(76)90037-6 1976

  14. [14]

    Galvin, The list chromatic index of a bipartite multigraph, J

    F. Galvin, The list chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B 63 (1995), 153-158

    work page 1995

  15. [15]

    Kalinowski, M

    R. Kalinowski, M. Pil´ sniak, and M. Wo´ zniak: Distinguishing graphs by total colourings,Ars Math. Contemp. 11 (2016), 79-89. doi: https://doi.org/10.26493/1855-3974.751.9a8

    work page doi:10.26493/1855-3974.751.9a8 2016

  16. [16]

    Kalinowski and M

    R. Kalinowski and M. Pil´ sniak, Distinguishing graphs by edge-colourings, European J. Comb. 45 (2015), 124–131

    work page 2015

  17. [17]

    Kazemi, Total dominator chromatic number of a graph, Trans

    A.P. Kazemi, Total dominator chromatic number of a graph, Trans. Combin. 4 (2015), no. 2, 57-68

    work page 2015

  18. [18]

    Kazemnejad and A.P

    F. Kazemnejad and A.P. Kazemi, Total dominator coloring of central graphs, Ars Comb. 155 (2021), 45-67

    work page 2021

  19. [19]

    Kazemnejad and S

    F. Kazemnejad and S. Moradi, Total domination number of central graphs, Bull. Korean Math. Soc. 56 (2019), 1059-1075

    work page 2019

  20. [20]

    Kazemnejad, B

    F. Kazemnejad, B. Pahlavsay, E. Palezzato, and M. Torielli, Total dominator coloring number of middle graphs, Discret. Math. Algorithms Appl. 15 (2023), doi: https://doi.org/10.1142/S1793830922500768

    work page doi:10.1142/s1793830922500768 2023

  21. [21]

    Kazemnejad, B

    F. Kazemnejad, B. Pahlavsay, E. Palezzato, and M. Torielli, Total domination number of middle graphs, Electron. J. Graph Theory Appl. 10 (2022), 275–288

    work page 2022

  22. [22]

    Y. Lu, J. Li, R. Luo, and Z. Miao, Adjacent vertex distinguishing total coloring of graphs with maximum degree 4, Discrete Math. 340 (2017), 119-123

    work page 2017

  23. [23]

    J. Lai, W. Yan, and X. Feng, On the number of perfect matchings of middle graphs, Discret. Appl. Math. 366 (2025), 86-91

    work page 2025

  24. [24]

    At´ ılio Luiz, C.N

    G. At´ ılio Luiz, C.N. Campos, and C.P. de Mello, AVD-total-colouring of complete equipartite graphs,Discret. Appl. Math. 184 (2015), 189-195

    work page 2015

  25. [25]

    S. M. Mirafzal, Some algebraic properties of the subdivision graph of a graph, Commun. Comb. Optim. 9 (2024) no. 2, 297-307. doi:https://doi.org/10.22049/cco.2023.28270.1494

    work page doi:10.22049/cco.2023.28270.1494 2024

  26. [26]

    Papaioannou and C

    A. Papaioannou and C. Raftopoulou, On the AVDTC of 4-regular graphs, Discrete Math. 330 (2014), 20-40

    work page 2014

  27. [27]

    Pedrotti and C

    V. Pedrotti and C. P. de Mello, Adjacent-vertex-distinguishing total coloring of indifference graphs, Matematica Contemporanea 39 (2010), 101-110

    work page 2010

  28. [28]

    B. S. Panda, S. Verma, and Y. Keerti, On the total and AVD-total coloring of graphs, AKCE Int J Graphs Co. 17 (2020), 820-825. doi:https://doi.org/10.1016/j.akcej.2019.10.004

    work page doi:10.1016/j.akcej.2019.10.004 2020

  29. [29]

    Pil´ sniak, Improving upper bounds for the distinguishing index, Ars Math

    M. Pil´ sniak, Improving upper bounds for the distinguishing index, Ars Math. Contemp. 13 (2017), 259–274. doi: https: //doi.org/10.26493/1855-3974.981.ff0

    work page doi:10.26493/1855-3974.981.ff0 2017

  30. [30]

    Sabidussi, Graph derivatives, Math

    G. Sabidussi, Graph derivatives, Math. Z. 76 (1961), 385–401

    work page 1961

  31. [31]

    J. V. Vernold, Harmonious coloring of total graphs, n-leaf, central graphs and circumdetic graphs, Ph.D Thesis, Bharathiar University, Coimbatore, India, 2007

    work page 2007

  32. [32]

    Verma, Hung-Lin Fu, and B

    S. Verma, Hung-Lin Fu, and B. S. Panda, Adjacent vertex distinguishing total coloring in split graphs, Discrete Math. 345 (2022)

    work page 2022

  33. [33]

    Vizing, Some unsolved problems in graph theory, Uspekhi Mat

    V.G. Vizing, Some unsolved problems in graph theory, Uspekhi Mat. Nauk. , 23 (1968), 117-134

    work page 1968

  34. [34]

    Wang, On the adjacent vertex-distinguishing total chromatic numbers of the graphs with ∆ = 3, J

    H. Wang, On the adjacent vertex-distinguishing total chromatic numbers of the graphs with ∆ = 3, J. Comb. Optim 14 (2007), 87-109

    work page 2007

  35. [35]

    Xie and Z

    D. Xie and Z. He, The total chromatic number of regular graphs of even order and high degree, Discrete Math. 300 (2005), 196-212

    work page 2005

  36. [36]

    H. P. Yap and K. H. Chew, Total chromatic number of graphs of high degree, II, J. Austral. Math. Soc. 53 (1992), 219-228

    work page 1992

  37. [37]

    Zhang, X

    Z. Zhang, X. Chen, J. Li, B. Yao, X. Lu, and J. Wang, On adjacent-vertex-distinguishing total coloring of graphs, Sci. China Ser. A 48 (2005), 289–299. ———————————————-

    work page 2005

  38. [38]

    Proof of Proposition 5.5

    Appendix 8.1. Proof of Proposition 5.5. In this section, we provide the proof of Proposition 5.5. 14 AMITAYU BANERJEE ∗, ALEXA GOPAULSINGH, AND ZAL ´AN MOLN ´AR (1). Let V = {vi : 1 ≤ i ≤ n} and U = {uj : 1 ≤ j ≤ m} be the set of vertices of G1 and G2 respectively. Let Gm = C(G2), Gn = C(G1), and G = C(G1 + G2). Without loss of generality, we assume that ...

    work page