Pith. sign in

REVIEW 2 major objections 6 minor 17 references

On Distinguishing Graphs and Cost Number using Automorphism Representations

T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read For every graph with determining number 2 and distinguishing number 2, the cost of a 2-distinguishing coloring is 2, 3, or 4, regardless of the graph's size.

desk verdict Main theorem settles Boutin's Det=2 case with a correct but under-proved key step; the missing argument is true and the paper deserves refereeing. read the letter →

arxiv 2505.21299 v2 pith:74JE2XLL submitted 2025-05-27 math.CO math.GR

Alexa Gopaulsingh , Zalán Molnár , Amitayu Banerjee This is my paper
classification math.COmath.GR MSC 05C1505C25
keywords distinguishingnumbercostdeterminingautomorphismrepresentationdistinguishableequivalencegraphautomorphisms2-distinguishablegraphs
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 proves that for every finite simple graph whose determining number is exactly 2 and whose distinguishing number is exactly 2, the cost of a 2-distinguishing coloring is 2, 3, or 4, no matter how many vertices the graph has. This settles, for $\mathrm{Det}(G)=2$, the open question of whether cost can be arbitrarily larger than determining number: it cannot. To reach this conclusion, the paper introduces the automorphism representation of a graph, the automorphism group written as explicit permutations of the labeled vertices, and shows that equal representations force equal distinguishing numbers. It also defines distinguishable equivalence classes of graphs and constructs a family of graphs suggesting that any bound for higher determining numbers, if it exists, would have to grow at least exponentially.

What carries the argument

The central object is the automorphism representation of a graph: for a fixed labeling, the set of permutations on the vertex labels induced by the graph's automorphisms. Two graphs with equal automorphism representations are distinguishably equivalent, meaning any coloring that breaks all non-identity permutations in one representation breaks the same permutations in the other, so the distinguishing number transfers. The main proof machinery is Lemma 3.2, quoted from the literature, which says a set of vertices is a distinguishing class exactly when it is a determining set and every automorphism fixing the set setwise also fixes it pointwise. This lemma lets the paper certify low cost by exhibiting 3- and 4-element sets with that property.

What would settle it

Find a finite simple graph with $D(G)=2$ and $\mathrm{Det}(G)=2$, a minimum determining pair $\{x,y\}$, and an automorphism $(xy)\alpha$ in which $\alpha$ consists only of transpositions and fixed points but contains no transposition swapping a neighbour-non-neighbour pair of $\{x,y\}$, while $(xy)$ itself is not an automorphism; that would falsify the key observation on which Theorem 3.15 relies. Alternatively, a computational search that produces any graph with $D(G)=2$, $\mathrm{Det}(G)=2$, and $\rho(G)>4$ would refute the theorem.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.15: if $D(G)=2$ and $\mathrm{Det}(G)=2$, then $2\le \rho(G)\le 4$. The proof fixes a minimum determining pair $\{x,y\}$. If no automorphism swaps $x$ and $y$, that pair itself is a distinguishing class and $\rho(G)=2$. If some automorphism $(xy)\alpha$ swaps them, Proposition 3.4 forces $\alpha$ to consist of transpositions and fixed points, and Lemma 3.12 rules out the case where $\alpha$ has no transpositions; the key observation then forces $\alpha$ to contain a transposition $(d_1d_2)$ with $(d_1,d_2)$ a neighbour-non-neighbour pair of $\{x,y\}$. The remaining case analysis shows that a 3-vertex or 4-vertex distinguishing class always exists, giving $\rho(G)\le 3$ or $\rho(G)\le 4$, while the lower bound $\rho(G)\ge 2$ follows because any distinguishing class is a determining set.

Load-bearing premise

The load-bearing premise is the unproved observation that an automorphism swapping the two determining vertices must also swap some pair of other vertices that are asymmetric with respect to them, one adjacent to exactly the first determining vertex and the other adjacent to exactly the second; every later case in the proof depends on this forcing, and if it fails the case analysis does not cover all graphs with determining number 2.

Editorial extensions

If this is right

  • If the theorem is correct, every graph with $D(G)=2$ and $\mathrm{Det}(G)=2$ can be told apart by coloring at most 4 of its vertices, independent of the graph's size.
  • The motivating open question is answered negatively for $\mathrm{Det}(G)=2$, leaving $\mathrm{Det}(G)\ge 3$ as the remaining open territory.
  • Two graphs with equal automorphism representations share their distinguishing number, and the same colorings distinguish both, so the new equivalence relation partitions graphs into classes where symmetry-breaking is interchangeable.
  • The proof leaves open whether the value 4 is actually attained; either such a graph exists or the upper bound can be improved to 3.
  • For graphs with determining number $2n-1$, the clique-with-paths construction forces any future bound to be at least $n2^{n-1}$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The transfer argument behind Theorem 2.10 preserves color-class sizes, so distinguishably equivalent 2-distinguishable graphs should also have equal cost $\rho$, not merely equal distinguishing number; the paper states only the latter.
  • The unproved observation inside Theorem 3.15, that an $(xy)$-swap containing no neighbour-non-neighbour transposition would force $(xy)$ itself to be an automorphism, is the step most worth testing by computer search.
  • A small exhaustive search over connected graphs could settle the open question of whether $\rho(G)=4$ ever occurs, because the theorem bounds any example to a 4-element distinguishing class.
  • The exponential lower-bound family contrasts sharply with the constant bound 4 for $\mathrm{Det}(G)=2$, suggesting that higher determining numbers, if bounded at all, will require bounds of a different scale.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 6 minor

Summary. The paper introduces the automorphism representation Aut(G,V(G)), a labeling-dependent permutation-group encoding of Aut(G), and shows that two graphs with equal automorphism representations have equal distinguishing numbers (Theorem 2.10). The main result is Theorem 3.15: if a finite simple graph G satisfies D(G)=2 and Det(G)=2, then its cost number satisfies 2≤ρ(G)≤4. The proof fixes a determining pair {x,y}, analyzes automorphisms extending the transposition (xy), and through a detailed case analysis (Cases 1a, 1b, 2a, 2b) constructs a distinguishing class of size at most 4. The paper also gives examples suggesting lower bounds for possible cost bounds when Det(G)>2.

Significance. The main theorem, if fully certified, is a clean resolution of an open problem posed by Boutin for the Det(G)=2 case: cost cannot be arbitrarily far from the determining number, and in fact is bounded by an absolute constant. The proof is self-contained and gives explicit distinguishing classes; it also showcases the utility of the automorphism-representation viewpoint. The paper is honest about the fact that no example with ρ(G)=4 is known. However, a load-bearing step in the proof of Theorem 3.15 is currently asserted without proof, and a supporting proposition in Section 2 is false as stated; these issues need to be repaired before the result is fully certified.

major comments (2)
  1. [Section 3, proof of Theorem 3.15, before Eq. (30)] The step 'We observe that if there exists an automorphism ... then this implies (xy)∈Aut(G)' is unproved. This observation is load-bearing: it is the only argument forcing the existence of a neighbour-non-neighbour pair (d1,d2) in Eq. (30), on which every subsequent case in the theorem depends. The implication is not immediate; it requires checking that if (xy)α∈Aut(G) and no 2-cycle of α is a neighbour-non-neighbour pair of {x,y}, then for every vertex v the adjacency of v to x equals the adjacency of v to y, so that (xy) alone preserves all edges. Please supply a proof.
  2. [Section 3, Lemma 3.12, Claim 3.13, n odd, k=0] In the k=0 subcase, after deriving (xy),(xv1),(yv1)∈Aut(G), the proof states that 'it is not possible to non-monochromatically color all of these consistently with only 2 colors' and concludes that G is not 2-distinguishable. This is true, but it is asserted rather than proved. With two colors, a coloring breaking both (xy) and (xv1) forces y and v1 to share the same color, so (yv1) is monochromatic. Since Lemma 3.12 is used to rule out the possibility α consisting only of single cycles in Theorem 3.15, this missing argument is load-bearing.
minor comments (6)
  1. [Section 2, Proposition 2.4(ii)] Proposition 2.4(ii) is false as stated: if G1 and G2 are two asymmetric graphs on different numbers of vertices, then Aut(G1,V(G1))=Aut(G2,V(G2))={id}. The proof's comparison of the 'length of single cycles' of l1(e) and l2(e) is invalid because both are the identity permutation on the common label set. This does not affect Theorem 3.15, but the statement should be corrected or the definition of automorphism representation refined (e.g., by including the support of the action).
  2. [Section 4, Example 4.1] The cost computation appears to assume 2^n clique vertices rather than 2n. For n=3, K6 with 2-edge paths attached has 18 vertices; one can assign six distinct 3-bit strings to the clique vertices and obtain a distinguishing 2-coloring whose smaller color class has far fewer than 12 vertices. The claimed value ρ(K^{p3}_{23})=12 therefore needs checking.
  3. [Definition 2.1] There is a typo in the cycle notation: the last cycle should be (vm1 vm2 ... v_{mk_m}).
  4. [Theorem 2.10 proof] The first sentence has a missing closing parenthesis and an incorrect subscript: it should read 'such that Aut(G1,V(G1)l1) = Aut(G2,V(G2)l2)'.
  5. [Section 3, Case 1a(ii)] Two typos: 'distinghuished' should be 'distinguished', and 'C5 cannot be distinghuished with 3 colors' should read '... with 2 colors' (since D(C5)=3).
  6. [Proposition 3.4] The statement says m,n∈N\{0}, but m (the number of 2-cycles in α) can be 0; the notation should allow m=0.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorem is derived from automorphism-group lemmas and an external standard lemma, not from its own conclusion.

full rationale

The paper's central claim, Theorem 3.15, is a finite case proof that Det(G)=2 and D(G)=2 force 2≤ρ(G)≤4. It does not fit any parameter to data, rename an input as a prediction, or rely on the authors' prior work. The only imported result is Lemma 3.2, cited from Boutin [9]; that is an external, published lemma about distinguishing classes and determining sets, and it is used in the standard direction (to translate between determining sets and distinguishing classes). The lower bound ρ(G)≥Det(G) follows from that lemma rather than being an input. The automorphism-representation framework in Section 2 is supporting terminology; Theorem 2.10 is proved directly via Lemma 2.8 and does not assume the target bound. The main proof's case analysis for (xy)α ∈ Aut(G) is built on earlier propositions (3.4–3.10) and Lemma 3.12, all proved within the paper. The proof does contain an unproved 'observe' before equation (30): if an automorphism flips x and y but flips no neighbour-non-neighbour pair, then (xy) alone would be an automorphism, contradicting Lemma 3.12. This is a genuine proof gap and a correctness risk, but it is not circularity: the assertion is a claimed property of automorphisms, not an assumption of the theorem's conclusion, and it does not reduce the result to a self-citation or to a fitted input. No circular step is present, so the appropriate score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central proof is self-contained apart from importing Lemma 3.2 from Boutin [9] and standard facts about automorphisms and edge preservation. The paper's main unproved premise is the 'observe' step in Theorem 3.15 that forces a neighbour-non-neighbour pair into the extension of (xy); this is listed as an ad hoc axiom. Proposition 2.4(ii) also contains an invalid proof, but it is not used in the main theorem. No free parameters or invented entities appear; the automorphism representation is a formal definition, not an extra object pulled from outside.

assumptions (3)
  • domain assumption A subset S is a distinguishing class for G iff S is a determining set and every automorphism that fixes S setwise fixes it pointwise (Lemma 3.2).
    Imported from Boutin [9] and used throughout the proof of Theorem 3.15, including in Claim 3.16 and the final case arguments.
  • ad hoc to paper If (xy)α is an automorphism and α contains no neighbour-non-neighbour pair of {x,y}, then (xy) is an automorphism.
    Stated without proof as an 'observe' in the proof of Theorem 3.15; it is needed to establish equation (30) and the subsequent case split.
  • standard math Standard facts about automorphisms: they preserve edges and non-edges, and the square of a product of disjoint transpositions is the identity.
    Used tacitly in Propositions 3.3 to 3.10 and in the case analysis.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Distinguishing Graphs and Cost Number using Automorphism Representations." pith.science (2026). https://pith.science/paper/74JE2XLL

@misc{pith2026250521299,
  author       = {Pith},
  title        = {Pith review of: On Distinguishing Graphs and Cost Number using Automorphism Representations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/74JE2XLL}},
  note         = {Machine review of arXiv:2505.21299}
}
abstract

A distinguishing coloring of a graph is a vertex coloring such that only the identity automorphism of the graph preserves the coloring. A 2-distinguishable graph is a graph which can be distinguished using 2 colors. The cost $\rho(G)$ of a 2-distinguishable graph is the smallest size of a color set of a distinguishing coloring of $G$. The determining number of a graph, $Det(G)$, is the minimum number of nodes, which if fixed by a coloring, would ensure that the coloring distinguishes the entire graph. Boutin (J. Combin. Math. Combin. Comput. 85: 161-171, 2013) posed an open problem which asks if $\rho(G)$ and $Det(G)$ can be arbitrarily far apart. It is trivial that it cannot be so for the case $Det(G) = 1$ but the answer was unknown for $Det(G) \geq 2$. We solve this problem for the case $Det(G) = 2$. We show that for the case $Det(G) = 2$, that not only is the cost bounded but in fact it takes small values with $\rho(G) = 2, \ 3$ or $4$. In order to establish this, the concept of the automorphism representation of a graph is developed. Graphs having equivalent automorphism representations implies that they have the same distinguishing number (note that just having isomorphic automorphism groups is not enough for this to hold). This prompts a factoring of graphs by which two graphs are distinguishably equivalent iff they have equivalent automorphism representations.

Figures

Figures reproduced from arXiv: 2505.21299 by the authors.

Figure 1
Figure 1. Two Distinguishably Equivalent Graphs. The automorphism representations for the graphs in [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Two Graphs with Isomorphic Automorphism Groups but Unequal [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. The graph K p3 2 3 . 5. Open Problems and Future Work 1. For fixed Det(G) ≥ 3, can ρ(G) be arbitrarily far from Det(G)? 2. We proved that for a graph G with D(G) = 2 and Det(G) = 2, that ρ(G) = 2, 3 or 4. It is easy to give examples for ρ(G) being 2 or 3, see the graphs G1 and G2 below. The blue circles represent (minimal) determining sets, while the reds represent cost nodes. G1 G2 However, we could not find an exa… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

17 extracted references · 15 canonical work pages

  1. [1]

    M. O. Albertson, D. L. Boutin,Distinguishing geometric graphs,J. Graph Theory, vol. 53(2) (2006), pp. 135–150, DOI:https://doi.org/10.1002/jgt.20171

    work page doi:10.1002/jgt.20171 2006

  2. [2]

    M. O. Albertson, D. L. Boutin,Using determining sets to distinguish Kneser graphs,Electron. J. Comb., vol. 14(1) (2007), DOI:https://doi.org/10.37236/938

    work page doi:10.37236/938 2007

  3. [3]

    M. O. Albertson, K. L. Collins,Symmetry breaking in graphs,Electron. J. Comb., vol. 3(1) (1996), DOI:https://doi.org/10.37236/1242

    doi:10.37236/1242 1996

  4. [4]

    Alikhani, S

    S. Alikhani, S. Soltani,The cost number and the determining number of a graph,J. Algebraic Syst., vol. 8 (2021)

    work page 2021

  5. [5]

    Babai,Asymmetric trees with two prescribed degrees,Acta Math

    L. Babai,Asymmetric trees with two prescribed degrees,Acta Math. Hung., vol. 29(1-2) (1977), pp. 193–200, DOI:https://doi.org/10.1007/BF01896481

    work page doi:10.1007/bf01896481 1977

  6. [6]

    Bogstad, L

    B. Bogstad, L. J. Cowen,The distinguishing number of the hypercube,Discrete Math., vol. 283(1-3) (2004), pp. 29–35, DOI:https://doi.org/10.1016/j.disc.2003.11.018

    work page doi:10.1016/j.disc.2003.11.018 2004

  7. [7]

    D. L. Boutin,Small label classes in 2-distinguishing labelings,Ars Math. Contemp., vol. 1(2) (2008), pp. 154–164, DOI:https://doi.org/10.26493/1855-3974.31.d93

    work page doi:10.26493/1855-3974.31.d93 2008

  8. [8]

    D. L. Boutin,The cost of 2-distinguishing Cartesian powers,Electron. J. Combin., vol. 20(1) (2013), DOI:https://doi.org/10.37236/3223

    work page doi:10.37236/3223 2013

Show all 17 references
  1. [9]

    D. L. Boutin,The cost of 2-distinguishing selected Kneser graphs and Hypercubes,J. Comb. Math. Comb. Comput., vol. 85 (2013), pp. 161–171, URL:https://combinatorialpress.com/ article/jcmcc/Volume%20085/vol-085-paper%2010.pdf

    2013

  2. [10]

    D. L. Boutin,The cost of 2-distinguishing Hypercubes,Discrete Math., vol. 344(9) (2021), DOI: https://doi.org/10.1016/j.disc.2021.112512

    2021

  3. [11]

    D. L. Boutin,Paint cost and the frugal distinguishing number,Art Discret. Appl. Math., vol. 6(2) (2021), DOI:https://doi.org/10.26493/2590-9770.1463.f59

    2021

  4. [12]

    Erwin, F

    D. Erwin, F. Harary,Destroying automorphisms by fixing nodes,Discrete Math., vol. 306(24) (2006), pp. 3244–3252, DOI:https://doi.org/10.1016/j.disc.2006.06.004

    2006 doi

  5. [13]

    Fukuda, S

    T. Fukuda, S. Negami,et al.,3-connected planar graphs are 2-distinguishable with few exceptions, Y okohama Math. J., vol. 54(2) (2008), pp. 1–11

    2008

  6. [14]

    C. R. Gibbons, J. D. Laison,Fixing Numbers of Graphs and Groups,Electron. J. of Combin., vol. 16(1) (2009), DOI:https://doi.org/10.37236/128

    2009 doi

  7. [15]

    Imrich, S

    W. Imrich, S. Klavžar,Distinguishing Cartesian powers of graphs,J. Graph Theory, vol. 53(3) (2006), pp. 250–260, DOI:https://doi.org/10.1002/jgt.20190

    2006 doi

  8. [16]

    Kalinowski, M

    R. Kalinowski, M. Pilśniak,Distinguishing graphs by edge-colourings,Eur. J. Comb., vol. 45 (2015), pp. 124–131, DOI:https://doi.org/10.1016/j.ejc.2014.11.003

    2015 doi

  9. [17]

    J. S. Tymoczko,Distinguishing numbers for graphs and groups,Electron. J. Combin., vol. 11(1) (2004), DOI:https://doi.org/10.37236/1816. Alexa Gopaulsingh: Department of Logic, Eötvös Loránd University, Budapest, Hungary Email: alexa279e@gmail.com Zalán Molnár: Department of Lo...

    2004 doi

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.