Pith. sign in

REVIEW 4 major objections 5 minor 38 references

Breaking Symmetry in Graphs by Resolving Sets

T0 review · 4 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read The paper proves that every connected graph satisfies D(G) at most dim(G)+1 and classifies all graphs whose distinguishing number is n(G), n(G)-1, or n(G)-2.

desk verdict The main bound D≤dim+1 is correct, but a systematic missing-\overline{K_t} notation error makes the Section 4 classifications false as written. read the letter →

arxiv 2412.15781 v2 pith:TKZNB4TL submitted 2024-12-20 math.CO

Meysam Korivand , Nasrin Soltankhah , Sandi Klavžar This is my paper · ORCID
classification math.CO MSC 05C1205C15
keywords resolvingsetmetricdimensiondistinguishingnumbertwingraphalmostasymmetricsymmetrybreakingunicyclicgraphsextremalclassification
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

This paper connects two ways of measuring a graph: the metric dimension $\dim(G)$, the fewest vertices whose distances determine every pair of vertices, and the distinguishing number $D(G)$, the fewest colors that leave no nontrivial symmetry. The main theorem is that every connected graph $G$ satisfies $D(G) \le \dim(G)+1$: take a smallest resolving set, give each of its vertices a distinct color, and give every other vertex one extra color; an automorphism preserving that coloring would fix the resolving set pointwise, but then any moved vertex would have identical distances to the resolving set as its image, contradicting resolution. The paper then proves that exactly the paths and the stars satisfy equality among trees, and exactly $C_3$, $C_4$, $C_5$ among connected unicyclic graphs, and it constructs graphs with $D(G)=n$ and $\dim(G)=m$ for every $1 \le n < m$. Using the bound together with a twin-graph reduction, it classifies all graphs with $D(G)=n(G)$, $D(G)=n(G)-1$, or $D(G)=n(G)-2$.

What carries the argument

The load-bearing object is the metric basis $S$. The paper's central move is to convert $S$ into a distinguishing coloring: each vertex of $S$ gets its own color, all other vertices share one extra color, and the resolving property does the rest; this is the mechanism behind $D(G) \le \dim(G)+1$. For the extremal classifications, the central reduction is the twin graph $G^*$, the quotient that identifies vertices with identical closed neighborhoods; it lets the paper test only small quotient graphs from the catalogues in Theorem 4.3 (diameter-2 graphs with $\dim(G)=n-3$) and Theorem 4.12 (diameter-$d$ graphs with $\dim(G)=n-d$). Within a twin class, a color-preserving automorphism can permute vertices, so the distinguishing number is largely controlled by the largest twin class, and the paper calls a graph almost asymmetric when no nontrivial automorphism moves a vertex between twin classes, making $D(G)$ exactly that largest class size.

What would settle it

Enumerate the twin graphs in the deferred cases (a2)--(a4), (b), and (c) of Theorem 4.12 for diameters 3 and 4, together with all possible twin-class sizes, and compute $D(G)$ for each; finding any graph other than $P_4$ with $D(G)=n(G)-2$ would falsify Lemma 4.13 and Theorem 4.14. The paper's own proof explicitly leaves these cases to 'techniques similar' to earlier lemmas, so this enumeration is the missing check.

Watch

Extended reading notes

Core claim

The central discovery is that resolving a graph also breaks its symmetries: every connected graph admits a distinguishing coloring with at most $\dim(G)+1$ colors, and the coloring is explicit. Assign distinct colors to the vertices of a metric basis and one further color to all vertices outside it. Because automorphisms preserve distances, a color-preserving automorphism must fix the basis pointwise; if it moved any other vertex $u$ to $v$, then $u$ and $v$ would have the same distance vector to the basis, which the resolving property forbids. The paper sharpens the bound: among trees, equality holds only for paths $P_n$ and stars $K_{1,n}$; among connected unicyclic graphs, only for $C_3$, $C_4$, $C_5$. Combined with known catalogues of graphs with metric dimension $n-2$ and $n-3$, the bound yields complete lists of graphs with $D(G)=n(G)$, $D(G)=n(G)-1$, and $D(G)=n(G)-2$.

Load-bearing premise

The load-bearing premise is Lemma 4.13's assertion that among connected graphs with diameter 3 or 4 and $\dim(G)=n(G)-d$, the only one with $D(G)=n(G)-2$ is the four-vertex path $P_4$; the proof defers the exclusion of cases (a2)--(a4), (b), and (c) to 'techniques similar' to earlier lemmas, so if one of those cases hides such a graph, the classification in Theorem 4.14 is incomplete.

Editorial extensions

If this is right

  • Every connected graph $G$ has a distinguishing coloring with at most $\dim(G)+1$ colors, so graphs with small metric dimension are automatically cheap to distinguish.
  • A tree attains $D(T)=\dim(T)+1$ only when it is a path $P_n$ or a star $K_{1,n}$; every other tree satisfies $D(T) \le \dim(T)$.
  • A connected unicyclic graph attains the bound $D(G)=\dim(G)+1$ only when it is $C_3$, $C_4$, or $C_5$; larger cycles and cycles with attached trees need at most $\dim(G)$ colors.
  • For every pair $1 \le n < m$ there is a graph with $D(G)=n$ and $\dim(G)=m$, so the metric dimension can exceed the distinguishing number by any prescribed amount.
  • The graphs with $D(G)=n(G)$, $n(G)-1$, and $n(G)-2$ are fully listed in Corollary 4.1, Theorem 4.2, and Theorem 4.14, closing the three largest possible values of $D(G)$.

Reading between the lines

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

  • Inference: the proof of the bound is constructive, so any algorithm that finds a metric basis also yields a distinguishing coloring with at most $\dim(G)+1$ colors; symmetry breaking is never more than one color harder than metric resolution.
  • Inference: the connectedness hypothesis in the inequality is essential to the argument as written; the paper reaches disconnected graphs only through complements, so extending the bound to disconnected graphs would need a separate mechanism.
  • Inference: the twin-graph enumeration pattern should carry over to the next case: given the recent catalogue of graphs with $\dim(G)=n-4$, the same lemmas could classify graphs with $D(G)=n-3$, the problem the paper's closing remark proposes.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper studies the relationship between two graph parameters: the metric dimension dim(G) and the distinguishing number D(G). Its central theorem (Proposition 3.1) states that every connected graph satisfies D(G) ≤ dim(G)+1, proved by coloring a metric basis with distinct colors and all other vertices with one additional color. It then characterizes trees and connected unicyclic graphs attaining equality, constructs graphs with prescribed values D(G)=n and dim(G)=m for any 1≤n<m, and uses the bound to classify graphs with D(G)=n(G)-2. The main inequality is correct and elegantly proved, but the classification sections contain a systematic notation error in the statement of the join of complete graphs, and several proofs in Sections 3 and 4 are incomplete or sketchy.

Significance. If the manuscript were corrected, the inequality D(G) ≤ dim(G)+1 would be a clean, useful new connection between two well-studied parameters, and the extremal classifications would be valuable additions to the literature. The paper also contains a useful construction showing that D(G) and dim(G) can be prescribed independently within the inequality range. However, the current version has load-bearing errors in the join notation and gaps in proofs of classification theorems, so the advertised results on graphs with D(G)=n(G)-2 and D(G)=n(G)-1 are not supported as written. The paper ships no code, but the main proof of Proposition 3.1 is a simple, verifiable argument; the gaps are in the surrounding structural work.

major comments (4)
  1. [Section 2, Theorem 2.3 and Proposition 2.4; Section 4, Theorem 4.14] Under the paper's own definition of the join G+H (Section 2: "making adjacent every vertex of G with every vertex of H"), the expression K_s + K_t denotes the complete graph K_{s+t}. Therefore Theorem 2.3, which claims dim(K_s + K_t) = n-2 for connected graphs, contradicts Theorem 2.2, which gives dim(K_{s+t}) = n-1. Likewise, the proof of Proposition 2.4 asserts D(K_s+K_t)=max{s,t}, which is false for a complete graph. Concretely, taking ℓ=1 and t=2 in Proposition 2.4(c) gives G=K_1+K_2=K_3, for which D(G)=3 but n-ℓ=2, so the claimed characterization fails. Consequently items (c)-(f) of Proposition 2.4 and the graphs (9) K_2+K_t and (11) K_t+K_2 in Theorem 4.14 are false as stated; for t=2 these entries would even include K_4 (or, under the likely intended correction K_2+\overline{K_t}, they would include C_4, which has D=3 and n=4 and thus does not satisfy D=n-2). The proofs of Theorems 4.2 and 4.14 rely on this flawed proposition, so the classifications are not supported. The intended statements presumably require complements on the second factor (e.g., K_s + \overline{K_t}) and adjusted parameter ranges, but that correction is not made in the manuscript.
  2. [Section 4, Lemma 4.13] The proof of Lemma 4.13 is incomplete in a load-bearing way. After treating case (a1), the proof states for cases (a2), (a3), (a4), (b), and (c) that "there are no graphs with distinguishing number n(G)-2" and says one can proceed by Corollary 4.5 for n(G*)≥5 and "techniques similar" to previous lemmas for n(G*)=4, without giving the actual arguments. Since this lemma is used in Theorem 4.14 to rule out all diameter-3 and diameter-4 graphs other than P_4, a missing case could add spurious graphs to the classification. The authors should supply the excluded-case check explicitly, as the referenced "similar" techniques are not identical for each case and the twin-class structure of G7–G10 does not directly cover G2(a2)-(a4), (b), or (c).
  3. [Section 3, Proposition 3.4] Proposition 3.4 asserts that for any 1≤n<m there exists a graph G with D(G)=n and dim(G)=m, but the proof is only a bare assertion for the case n≥2. The graph G_{n,m} obtained from T_{m-n+2} and K_n by joining the maximum-degree vertex of T to all vertices of K_n is introduced, and the statements D(G_{n,m})=n and dim(G_{n,m})=m are declared without proof. This is a central advertised result of the paper, so the computation of both parameters (or at least a clear argument for the distinguishing number, including the case where the automorphism group of T could interact with the K_n part) must be provided.
  4. [Section 3, Theorem 3.3, second case] The proof of the second case of Theorem 3.3 (where at least one T_i is not a path) is too sketchy to verify. The paragraph starting "If a non-trivial automorphism f preserves this coloring" argues that changing the color of s_1 and t_1 to 2 (so that the color-2 class contains s_1, s_2, t_1) yields a distinguishing coloring with dim(G) colors, but it does not show that the resulting coloring admits no color-preserving non-trivial automorphism. In particular, the argument does not rule out an automorphism that swaps s_1 with t_1 while fixing s_2, nor does it justify why the presence of t_2 and t_m in the cycle forces the claimed behavior. This gap affects the characterization of unicyclic graphs attaining the bound, and the proof needs to be made rigorous.
minor comments (5)
  1. [Throughout] There are several typos and grammatical slips: "the concepts was reinvented" in the Introduction, "if G be a graph" in Theorem 4.14, and "we have arived" at the start of Section 4.
  2. [Section 4, Theorem 4.14] The list of graphs in Theorem 4.14 contains duplicate entries: for t=2, items (9) K_2+K_t and (11) K_t+K_2 coincide, and the same likely happens under the intended notation; the statement should avoid this ambiguity.
  3. [Section 3, Theorem 3.2] In the proof of the case ex(T)≥2, the text says to color external leaves of b_i with distinct colors from [deg_T(b_i)], but the palette should be [t]; the number of leaves of b_i is at most deg(b_i)-1 ≤ t, so the intended coloring is achievable, but as written it suggests using potentially more than t colors.
  4. [Section 3, Theorem 3.3] In the first case of Theorem 3.3, when m∈{3,4,5} and the colorings for paths with at least two vertices are given, the sentence "Note that the above argument is also applicable as soon as at least one T_i has at least two vertices" is not demonstrated; the singleton cases should be checked explicitly.
  5. [References] Reference [26] has a duplicated year, "J. Algebra 303 (2006) (2006) 626–641", and reference [34] is missing a period after "metric dimension, its applications".

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central bound and classifications are derived from external theorems and direct coloring constructions.

full rationale

The paper's central claim, Proposition 3.1, is proved directly: a metric basis is colored with distinct colors and all other vertices receive one additional color, and any color-preserving automorphism would fix the basis pointwise and hence be forced to identify two vertices that the basis resolves — a contradiction. This argument does not assume the conclusion and does not rely on self-citation. The equality characterizations for trees and unicyclic graphs use the standard external tree metric-dimension formula and explicit distinguishing colorings, so they are independent constructions. The classifications in Section 4 rest on external characterizations of graphs with large metric dimension (Theorems 2.2, 2.3, 4.3, 4.12, citing Chartrand et al., Jannesari–Omoomi, and Hernando et al.), combined with direct computations of distinguishing numbers in Proposition 2.4 and Lemmas 4.6–4.11. The self-citations in the paper ([17], [25], [26]) appear in the introduction and background discussion and are not used to prove the main bound or the subsequent classifications. Lemma 4.13 does leave some cases to 'techniques similar' to earlier lemmas, but that is a completeness gap in the proof rather than a circular dependence: the excluded cases are checked by the same kind of direct distinguishing-number computations, not by assuming the result. The skeptic's notation concern about K_s + K_t being K_{s+t} under the paper's join definition is a correctness issue (the intended graph may require complement bars), not a circularity: the derivation is not equivalent to its inputs by construction. Overall, the derivation chain is self-contained against external, independently established results, and no fitted parameter is renamed as a prediction. Therefore no circular step is identified.

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

The central claims rest on established graph theory classifications and the standard metric dimension formula for trees. No free parameters are fitted to data, and no new entities are postulated. The main external dependencies are Theorem 2.3, Theorem 4.3, and Theorem 4.12.

assumptions (6)
  • domain assumption Theorem 2.2: dim(G)=n(G)-1 iff G=K_n (Chartrand et al.)
    Used in Section 4 to restrict the metric dimension of graphs with D(G)=n(G)-2.
  • domain assumption Theorem 2.3: classification of connected graphs with dim(G)=n(G)-2
    Foundation for Proposition 2.4 and the classification theorem.
  • domain assumption Formula dim(T)=l(T)-ex(T) for trees not paths
    Used in Theorem 3.2 and Proposition 3.4; from Slater and Harary-Melter.
  • domain assumption Theorem 4.3: classification of connected graphs with diam=2 and dim=n-3 (Jannesari-Omoomi)
    Used in Theorem 4.14 for the dim=n-3 case.
  • domain assumption Theorem 4.12: classification of connected graphs with diam>=3 and dim=n-d (Hernando et al.)
    Used in Lemma 4.13.
  • domain assumption [14, Corollary 7] allows assuming t1 not in S for unicyclic graphs
    Used in Theorem 3.3 second case to adjust the metric basis.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Breaking Symmetry in Graphs by Resolving Sets." pith.science (2026). https://pith.science/paper/TKZNB4TL

@misc{pith2026241215781,
  author       = {Pith},
  title        = {Pith review of: Breaking Symmetry in Graphs by Resolving Sets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TKZNB4TL}},
  note         = {Machine review of arXiv:2412.15781}
}
abstract

Let ${\rm dim}(G)$ and $D(G)$ respectively denote the metric dimension and the distinguishing number of a graph $G$. It is proved that $D(G) \le {\rm dim}(G)+1$ holds for every connected graph $G$. Among trees, exactly paths and stars attain the bound, and among connected unicyclic graphs such graphs are $t$-cycles for $t\in \{3,4,5\}$. It is shown that for any $1\leq n< m$, there exists a graph $G$ with $D(G)=n$ and ${\rm dim}(G)=m$. Using the bound $D(G) \le {\rm dim}(G)+1$, graphs with $D(G) = n(G)-2$ are classified.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 33 canonical work pages

  1. [1]

    Ahmadi, F

    B. Ahmadi, F. Alinaghipour, M. H. Shekarriz, Number of distinguishing color- ings and partitions, Discrete Math. 343 (2020) 111984

    work page 2020

  2. [2]

    M. O. Albertson, K. L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996) Paper 18

    work page 1996

  3. [3]

    Arumugam, V

    S. Arumugam, V. Mathew, The fractional metric dimension of graphs, Discrete Math. 312 (2012) 1584–1590

    work page 2012

  4. [4]

    Babai, Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker’s Conjecture confirmed, J

    L. Babai, Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker’s Conjecture confirmed, J. Algebra 607 (2022) 64–106

    work page 2022

  5. [5]

    Babai, Asymmetric trees with two prescribed degrees, Acta Math

    L. Babai, Asymmetric trees with two prescribed degrees, Acta Math. Acad. Sci. Hungar. 29 (1977) 193–200

    work page 1977

  6. [6]

    R. F. Bailey, P. J. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bull. London Math. Soc. 43 (2011) 209–242

    work page 2011

  7. [7]

    D. L. Boutin, Determining sets, resolving sets, and the exchange property, Graphs Combin. 25 (2009) 789–806

    work page 2009

  8. [8]

    Chan, The distinguishing number of the direct product and wreath product action, J

    M. Chan, The distinguishing number of the direct product and wreath product action, J. Algebraic Combin. 24 (2006) 331–345

    work page 2006

Show all 38 references
  1. [9]

    Chartrand, L

    G. Chartrand, L. Eroh, M. A. Johnson, O. R. Ollermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000) 99–113

    2000

  2. [10]

    K. L. Collins, A. N. Trenk, The distinguishing chromatic number, Electron. J. Combin. 13 (2006) Paper R16. 14

    2006

  3. [11]

    K. L. Collins, A. N. Trenk, The distinguishing number and distinguishing chro- matic number for posets, Order 39 (2022) 361–380

    2022

  4. [12]

    Estrada-Moreno, I

    A. Estrada-Moreno, I. G. Yero, J. A. Rodr ´ ıguez-Vel´ azquez, Thek-metric di- mension of a graph, Appl. Math. Inf. Sci. 9 (2015) 2829–2840

    2015

  5. [13]

    Garijo, A

    D. Garijo, A. Gonz´ alez, A. M´ arquez, The difference between the metric dimen- sion and the determining number of a graph, Appl. Math. Comput. 249 (2014) 487–501

    2014

  6. [14]

    Hakanen, V

    A. Hakanen, V. Junnila, T. Laihonen, I. G. Yero, On vertices contained in all or in no metric basis, Discrete Appl. Math. 319 (2022) 407–423

    2022

  7. [15]

    Harary, R

    F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195

    1976

  8. [16]

    Hernando, M

    C. Hernando, M. Mora, I. M. Pelayo, C. Seara, D. R. Wood, Extremal graph theory for metric dimension and diameter, Electron. J. Combin. 17 (2010) Paper R30

    2010

  9. [17]

    Imrich, S

    W. Imrich, S. Klavˇ zar. Distinguishing Cartesian powers of graphs, J. Graph Theory 53 (2006) 250–260

    2006

  10. [18]

    Jannesari, B

    M. Jannesari, B. Omoomi, Characterization of n-vertex graphs with metric dimension n − 3, Math. Bohem. 139 (2014) 1–23

    2014

  11. [19]

    Jannesari, B

    M. Jannesari, B. Omoomi. The metric dimension of the lexicographic product of graphs, Discrete Math. 312 (2012) 3349–3356

    2012

  12. [20]

    Kalinowski, M

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

    2015

  13. [21]

    Kalinowski, M

    R. Kalinowski, M. Pil´ sniak, M. Prorok, Distinguishing arc-colourings of sym- metric digraphs, Art Discrete Appl. Math. 6 (2023) Paper P2.04

    2023

  14. [22]

    Kelenc, D

    A. Kelenc, D. Kuziak, A. Taranenko, I. G. Yero, Mixed metric dimension of graphs, Appl. Math. Comput. 314 (2017) 429–438

    2017

  15. [23]

    Kelenc, N

    A. Kelenc, N. Tratnik, I. G. Yero, Uniquely identifying the edges of a graph: the edge metric dimension, Discrete Appl. Math. 251 (2018) 204–220

    2018

  16. [24]

    Khuller, B

    S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217–229. 15

    1996

  17. [25]

    Klavˇ zar, D

    S. Klavˇ zar, D. Kuziak, Nonlocal metric dimension of graphs, Bull. Malays. Math. Sci. Soc. 46 (2023) Paper 66

    2023

  18. [26]

    Klavˇ zar, T.-L

    S. Klavˇ zar, T.-L. Wong, X. Zhu, Distinguishing labellings of group action on vector spaces and graphs, J. Algebra 303 (2006) (2006) 626–641

    2006

  19. [27]

    Kuziak, I

    D. Kuziak, I. G. Yero, Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results, arXiv:2107.04877 [math.CO] (2021)

    2021 arXiv

  20. [28]

    Okamoto, B

    F. Okamoto, B. Phinezy, P. Zhang, The local metric dimension of a graph, Math. Bohem. 135 (2010) 239–255

    2010

  21. [29]

    Russell, R

    A. Russell, R. Sundaram, A note on the asymptotics and computational com- plexity of graph distinguishability, Electron. J. Combin. 5 (1998) Paper R23

    1998

  22. [30]

    Seb¨ o, E

    A. Seb¨ o, E. Tannier, On metric generators of graphs, Math. Oper. Res. 29 (2004) 383–393

    2004

  23. [31]

    Shanmukha, B

    B. Shanmukha, B. Sooryanarayana, K.S. Harinath, Metric dimension of wheels, Far East J. Appl. Math. 8 (2002) 217–229

    2002

  24. [32]

    M. H. Shekarriz, B. Ahmadi, S. A. Talebpour, M. H. Shirdareh Haghighi, Dis- tinguishing threshold of graphs, J. Graph Theory 103 (2023) 359–377

    2023

  25. [33]

    P. J. Slater, Leaves of trees, Congress. Numer. 14 (1975) 549–559

    1975

  26. [34]

    R. C. Tillquist, R. M. Frongillo, M. E. Lladser. Getting the lay of the land in discrete space: A survey of metric dimension, its applications. SIAM Rev. 65 (2023) 919–962

    2023

  27. [35]

    Trujillo-Ra´ sua, I

    R. Trujillo-Ra´ sua, I. G. Yero, k-metric antidimension: A privacy measure for social graphs, Inf. Sci. 328 (2016) 403–417

    2016

  28. [36]

    T. W. Tucker, Distinguishing maps, Electron. J. Combin. 18 (2011) Paper 50

    2011

  29. [37]

    Tymoczko, Distinguishing numbers for graphs and groups, Electron

    J. Tymoczko, Distinguishing numbers for graphs and groups, Electron. J. Com- bin. 11 (2004) Paper R63

    2004

  30. [38]

    J. Wang, F. Tian, Y. Liu, J. Pang, L. Miao, On graphs of order n with metric dimension n − 4, Graphs Combin. 39 (2023) Paper 29. 16

    2023

Pith tools

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