pith. sign in

arxiv: 2507.16301 · v3 · pith:6C4DF7SMnew · 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 this result to obtain new upper bounds of the distinguishing number and the distinguishing index of C(G) and M(G) and provide examples showing that these bounds cannot be improved in general. Moreover, we use idempotent commutative Latin squares and a theorem of Galvin on list edge colorings of bipartite graphs to study the total distinguishing chromatic number of central graphs.

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.