Pith. sign in

REVIEW 5 major objections 4 minor 25 references

Intertwining local (adjacency) metric dimension with the clique number of a graph

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

Pith's one-line read The local adjacency metric dimension of any non-complete connected graph with clique number $\omega$ is at most $\left\lfloor \frac{\omega-2}{\omega-1}\,n \right\rfloor$, confirming a conjecture for all clique numbers.

desk verdict A plausible theorem and a correct equality family, but the proof has a load-bearing off-by-one that skips K_omega blocks; needs a rewrite before it can be accepted. read the letter →

arxiv 2507.13777 v1 pith:V4JULZ2Y submitted 2025-07-18 math.CO

classification math.CO MSC 05C1205C69
keywords metricdimensionlocaladjacencycliquenumberresolvingsetextremalgraphtheory
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 proves that for every connected, non-complete graph $G$ whose clique number $\omega(G)$ is at least $3$, the local adjacency metric dimension obeys $\dim_{A,l}(G) \le \left\lfloor \frac{\omega(G)-2}{\omega(G)-1}\, n(G) \right\rfloor$. Because the ordinary local metric dimension is never larger than the local adjacency metric dimension, the same expression is an upper bound for $\dim_l(G)$, which confirms the previously open Conjecture 1.1. The proof constructs an explicit local adjacency resolving set of that size by peeling disjoint subgraphs of prescribed clique-like shapes, and it exhibits infinitely many graphs where the bound is attained. This gives a clean, parameter-dependent upper bound that is tight for a whole family.

What carries the argument

The proof rests on a layered greedy decomposition. It first fixes a maximum collection of vertex-disjoint induced subgraphs of $G$ isomorphic to $K^{-i}_{\omega(G)+1}$, the complete graph on $\omega(G)+1$ vertices with $i$ edges incident to a common vertex removed, for $i=1,\dots,\omega(G)-1$, and then fills the remaining vertices with maximum collections of disjoint cliques $K_j$ of descending sizes. Passing through these layers, the construction builds a set $S$ by adding whole blocks or all but one or two specified vertices of a block, depending on how many still-available $K_\omega$ blocks are adjacent to the current block. The size accounting uses the per-layer inequality $\frac{\omega(G)-2}{\omega(G)-1}\,r \ge r-1$, and the resolving property is checked by a series of maximality facts about the decomposition, which force every adjacent pair to be separated by some vertex of $S$. The ratio $\frac{\omega-2}{\omega-1}$ emerges from leaving exactly two vertices out of certain $K_\omega$ blocks and one or two vertices out of certain $K^{-i}_{\omega+1}$ blocks.

What would settle it

Compute, by exhaustive search, the local adjacency metric dimension of every connected graph on up to nine vertices; if any graph $G$ with $n(G) \ge \omega(G)+1 \ge 4$ has $\dim_{A,l}(G) > \left\lfloor \frac{\omega(G)-2}{\omega(G)-1}\,n(G) \right\rfloor$, the theorem is false, while the shared-clique family should appear with equality in the same search.

Watch

Extended reading notes

Core claim

The central discovery is that the clique number alone controls the local adjacency metric dimension up to a fraction $\frac{\omega(G)-2}{\omega(G)-1}$ of the order. More precisely, whenever $G$ is connected, $n(G) \ge \omega(G)+1 \ge 4$, and $G$ is not a complete graph, there is a local adjacency resolving set $S$ of size at most $\left\lfloor \frac{\omega(G)-2}{\omega(G)-1}\, n(G) \right\rfloor$. Since $\dim_l(G) \le \dim_{A,l}(G)$, the conjectured bound $\dim_l(G) \le \left\lfloor \frac{\omega(G)-2}{\omega(G)-1}\, n(G) \right\rfloor$ follows for every clique number, unifying cases that had only been settled for clique number $3$, clique number $4$, and clique numbers close to $n(G)$. The bound is best possible in infinite families: the graph obtained by identifying one vertex from each of $t$ copies of $K_\omega$ has dimension exactly $t(\omega-2)$, matching the formula.

Load-bearing premise

The construction assumes that whenever it decides to use a vertex $x$ from a $K^{-i}_{\omega+1}$ block together with an adjacent $K_\omega$ block $Y$, the block $Y$ contains two vertices $y_1,y_2$ such that $\{x,y_1,y_2\}$ forms a path on three vertices; if some adjacency pattern fails to supply such a pair, the set $S$ is not well-defined and the resolving-set argument stops.

Editorial extensions

If this is right

  • The conjecture on local metric dimension is now a theorem for all clique numbers, so the earlier special cases are covered by one argument.
  • For any graph satisfying the hypotheses, a local metric resolving set of size at most $\left\lfloor \frac{\omega-2}{\omega-1}\,n \right\rfloor$ exists, so graphs with large clique number cannot have local metric dimension close to $n$ unless they are close to complete graphs.
  • The bound is tight for infinitely many graphs, namely $t$ copies of $K_\omega$ sharing one common vertex, so the constant $\frac{\omega-2}{\omega-1}$ cannot be improved in general.
  • Because the proof constructs $S$ explicitly, it yields a concrete upper bound for both $\dim_l(G)$ and $\dim_{A,l}(G)$, not merely an existence statement.

Reading between the lines

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

  • Editorial extension: the same layer-counting may characterize all equality cases or show that equality forces a block structure close to the shared-clique family; the paper only exhibits the extremal family.
  • Editorial extension: although the proof bounds the local adjacency dimension, a similar peeling strategy might bound the non-local adjacency metric dimension on dense graphs, but that would require a separate argument because non-local resolving sets must separate all pairs, not just adjacent pairs.
  • Editorial extension: the constructive resolving set can likely be produced by a polynomial-time greedy algorithm if the decomposition steps can be certified, which would give an algorithmic guarantee rather than only an extremal bound.
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

5 major / 4 minor

Summary. The paper proves (or claims to prove) that for a simple connected graph G with clique number ω(G) ≥ 3 and n(G) ≥ ω(G)+1, the local adjacency metric dimension satisfies dim_{A,l}(G) ≤ floor(((ω(G)-2)/(ω(G)-1)) n(G)). Since dim_l(G) ≤ dim_{A,l}(G), this confirms Conjecture 1.1 for the local metric dimension. The proof partitions V(G) into maximum families of vertex-disjoint induced subgraphs of the forms K^{-i}_{ω(G)+1} and K_j, constructs a set S through 2ω(G)-3 processes, and asserts that S is a local adjacency resolving set with the desired cardinality. An infinite family G_{t,ω} is given to show equality is attained.

Significance. If the proof were complete, the result would be significant: it confirms a known conjecture for all clique numbers, unifying and extending the previously known cases ω(G)=3 and ω(G)=4. The equality construction G_{t,ω} is correct and shows the bound is sharp for infinitely many graphs. However, the present manuscript does not supply a complete proof: the resolving property and the cardinality bound are asserted in one sentence, several existential choices in the construction are not justified, and the role of the K_ω blocks in the third phase is not established. These gaps are load-bearing for the main theorem.

major comments (5)
  1. [§2, final paragraph] The claim that the constructed set S is a local adjacency resolving set is not proved. After the construction, the paper states that 'by utilizing (I)-(V) and applying the methods used to construct S, we can confirm that S is a local adjacency resolving set for G,' but no case analysis is given for adjacent pairs within each block type (K^{-i}_{ω+1} blocks, K_ω blocks in Y, K_j blocks with j<ω, isolated vertices) or between different blocks. This is the central assertion of Theorem 1.5 and requires a detailed verification.
  2. [§2, final paragraph] The cardinality bound |S| ≤ ((ω(G)-2)/(ω(G)-1)) n(G) is also only asserted. The quantities ξ_t are defined and some inequalities are listed, but the text never connects these inequalities to the number of vertices added in each case of the Γth processes, nor does it sum the contributions over all blocks K_i(G) and over the Y-blocks. A rigorous counting argument must be supplied.
  3. [§2, third Γth process] The third set of processes, for Γ ranging from ω(G) to 2ω(G)-3, uses V(X^{Γ+1}_i), so it processes only the blocks K_{ω-1}, K_{ω-2}, …, K_2 and never the K_ω blocks. The K_ω blocks are meant to be handled through the set Y in the first two phases, but the text does not prove that every block in Y is eventually removed from Y (i.e., has an edge to some processed K^{-i}_{ω+1} block). If a K_ω block remained in Y, no vertex from it would be added to S, and edges inside that clique could remain unresolved. The proof must either show that the first two phases exhaust Y or modify the construction to process K_ω blocks.
  4. [§2, (1.5), (1.6), (Γ.4), (Γ.6)] Several steps of the construction assume the existence of vertices with certain properties without proof. For example, (1.5) requires an element l ∈ [ω(G)+1] for which removing x^1_{il} leaves a subgraph connected to Y_1 ∪ Y_2; (1.6) and (Γ.6) require a vertex z such that G[{x^1_{iz}, y^l_1, y^l_2}] ≅ P_3; and (Γ.4) requires l_1 ∈ [ω(G)] such that E_G(G[V(X^Γ_i) - {x^Γ_{il_1}}], Y_1) ≠ ∅. If any of these choices does not exist for some graph, the set S is not well-defined. The authors need to prove that conditions (I)-(V) guarantee these choices, or introduce and justify additional conditions.
  5. [§2, conditions (I)-(V)] Conditions (I)-(V) are stated as consequences of the maximality of the K_i(G) families, but no derivation is provided. Condition (V), in particular, is a strong structural assertion: for every vertex x of a K^{-i}_{ω+1} block and every vertex y of a K_ω block, there is a vertex z in the same K_ω block such that {x,y,z} induces a P_3. Since the resolving-set verification and the counting argument are supposed to rely on these conditions, they need to be proved or at least derived in detail.
minor comments (4)
  1. [§2, (Γ.2) and (Γ.3)] The notation in the third Γth process is confusing: '(Γ.2)' contains the string '|KΓ(G)+1|', which should presumably be '|K_{Γ+1}(G)|', and '(Γ.3)' contains the undefined symbol 'hΓ_iω(G)−Γ+1', which should be 'xΓ_iω(G)−Γ+1'.
  2. [§1, definitions] The sentence 'If S ⊆ V(G) and S = V(G) \ S' is garbled; it should read 'If S ⊆ V(G) and \overline{S} = V(G) \setminus S'. Consequently, the phrases 'from S' in the bullet points should be checked against the intended definition (presumably 'from \overline{S}' or 'from V(G)').
  3. [§2, opening of the proof] The proof begins with 'Let G be a graph with n(G) ≥ ω(G) + 1 ≥ 5', but Theorem 1.5 states the hypothesis n(G) ≥ ω(G)+1 ≥ 4. The authors should explicitly say that the case ω(G)=3 is handled by Theorem 1.3 before starting the construction.
  4. [§2, (1.3)] The notation 'x^1_{iω(G)}' in (1.3) should be 'x^1_{i,ω(G)}' (with a comma) to match the indexing convention used elsewhere.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the constructive bound is derived from vertex partitioning and counting, with the ω=3 case imported as independent prior support.

full rationale

The paper proves Theorem 1.5 by an explicit construction: it partitions V(G) into vertex-disjoint blocks isomorphic to K^{-i}_{ω+1} or K_j, then runs 2ω−3 processes that add vertices to a set S. The claimed size bound |S| ≤ ((ω−2)/(ω−1)) n(G) follows by counting how many vertices each process adds per block, and the claim that S is a local adjacency resolving set is argued from the structural consequences (I)–(V), which are derived from maximality of the block families and the definition of ω(G). There are no fitted parameters, no quantity is defined in terms of the target bound, and no 'prediction' is read back from an input. The only self-citations are to prior work by the same authors: Theorem 1.3 from [11] supplies the ω=3 case of the bound, and the proof strategy of [12] is borrowed for larger ω. These are parameter-free stated results whose assumptions do not include the full target theorem; citing them is normal incremental research, not circularity. The sharpness example G_{t,ω} is used only to exhibit equality and is not an input to the upper-bound proof. Separately, there may be a mathematical gap in the proof—for instance, the third construction phase never directly processes K_ω blocks, and the existence of the P3 choices in Steps 1.4–1.6 and Γ.4–Γ.6 is asserted without proof—but a correctness gap is not circular reasoning: no step of the derivation is equivalent to its own input by construction. Hence the circularity score is 0.

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

The proof rests on standard graph theory definitions, a finite maximality argument, the cited ω=3 base case, and the paper's own unproved adjacency conditions (I)-(V). No free parameters or invented entities are introduced.

assumptions (4)
  • domain assumption G is finite, simple, connected, G not isomorphic to K_n, and ω(G) ≥ 3
    Stated in the abstract and Section 1; the theorem and the construction only apply under these conditions.
  • standard math For every finite graph, a maximum set of vertex-disjoint induced subgraphs of a given isomorphism type exists
    Used in Section 2 to define the K_i(G) sets; follows directly from finiteness and is not proved in the paper.
  • standard math Theorem 1.3 from [11]: for graphs with ω(G)=3, dim_{A,l}(G) ≤ floor(n(G)/2)
    Used as the base case ω=3 in the proof of Theorem 1.5; the paper does not reprove this result.
  • ad hoc to paper The adjacency conditions (I)-(V) are valid consequences of the maximality of the K_i(G) sets
    Stated without proof in Section 2 ('we can derive the following results') and used to justify the existence of choices in the construction and the resolving property of S. If any of these conditions fail, the proof collapses.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Intertwining local (adjacency) metric dimension with the clique number of a graph." pith.science (2026). https://pith.science/paper/V4JULZ2Y

@misc{pith2026250713777,
  author       = {Pith},
  title        = {Pith review of: Intertwining local (adjacency) metric dimension with the clique number of a graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V4JULZ2Y}},
  note         = {Machine review of arXiv:2507.13777}
}
abstract

Let $G$ be a simple connected graph with order $ n(G)$, local metric dimension $ {\rm dim}_l(G)$, local adjacency metric dimension $ {\rm dim}_{A,l}(G)$, and clique number $ \omega(G)$, where $G\not\cong K_{n(G)}$ and $\omega(G)\geq3$. It is proved that $ {\rm dim}_{A,l}(G) \leq \left\lfloor \left(\frac{\omega(G) - 2}{\omega(G) - 1}\right)n(G)\right\rfloor$. Consequently, the conjecture asserting that the latter expression is an upper bound for ${\rm dim}_l(G)$ is confirmed. It is important to note that there are infinitely many graphs that satisfy the equalities.

Figures

Figures reproduced from arXiv: 2507.13777 by the authors.

Figure 1
Figure 1. The graphs K−i 4 for i ∈ [2] and K −j 5 for j ∈ [3]. While this selection may not be unique, we will choose a specific selection and fix it for the purpose of this proof. This will ensure that the following notation is well-defined. • Let K1(G) be a maximum set of vertex disjoint induced subgraphs of G iso￾morphic to K−1 ω(G)+1, and set G1 = G. • For i = 2, . . . , ω(G)−1, let Ki(G) be a maximum set of vertex disjoi… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

25 extracted references · 24 canonical work pages

  1. [1]

    Abrishami, M

    G. Abrishami, M. A. Henning, M. Tavakoli, Local metric dimension for graphs with small clique numbers, Discrete Math. 345 (2022) Paper 112763

  2. [2]

    Barrag´ an-Ram ´ ırez, A

    G.A. Barrag´ an-Ram ´ ırez, A. Estrada-Moreno, Y. Ram ´ ırez-Cruz, J.A. Rodr ´ ıguez-Vel´ azquez, The local metric dimension of the lexicographic product of graphs, Bull. Malays. Math. Sci. Soc. 42 (2019) 2481–2496

  3. [3]

    Barrag´ an-Ram ´ ırez, J.A

    G.A. Barrag´ an-Ram ´ ırez, J.A. Rodr ´ ıguez-Vel´ azquez, The local metric dimension of strong product graphs, Graphs Combin. 32 (2016) 1263–1278

  4. [4]

    Bermudo, J.M

    S. Bermudo, J.M. Rodr ´ ıguez, J.A. Rodr ´ ıguez-Vel´ azquez, J.M. Sigarreta, The adjacency dimension of graphs, Ars Math. Contemp. 22 (2022) Paper 2

  5. [5]

    J. Diaz, O. Pottonen, M. Serna, E.J. van Leeuwen, Complexity of metric di- mension on planar graphs, J. Comput. Syst. Sci. 83 (2017) 132–158

  6. [6]

    Fernau, J.A

    H. Fernau, J.A. Rodr ´ ıguez-Vel´ azquez, On the (adjacency) metric dimension of corona and strong product graphs and their local variants, combinatorial and computational results, Discrete Appl. Math. 236 (2018) 183–202

  7. [7]

    Fernau, J.A

    H. Fernau, J.A. Rodr ´ ıguez-Vel´ azquez, Notions of metric dimension of corona products: combinatorial and computational results, Lecture Notes Comput. Sci. 8476 (2014) 153–166. 10

  8. [8]

    Fitriani, S.W

    D. Fitriani, S.W. Saputro, The local metric dimension of amalgamation of graphs, Electron. J. Graph Theory Appl. (EJGTA) 12 (2024) 125–146

Show all 25 references
  1. [9]

    Ghalavand, M

    A. Ghalavand, M. A. Henning, M. Tavakoli, On a conjecture about the local metric dimension of graphs, Graphs Combin. 39 (2023) Paper 5

  2. [10]

    Ghalavand, S

    A. Ghalavand, S. Klavˇ zar, X. Li, Interplay between the local metric dimension and the clique number of a graph,arXiv:2412.17074 [math.CO] (22 Dec 2024)

  3. [11]

    Ghalavand, S

    A. Ghalavand, S. Klavˇ zar, X. Li, On the local metric dimension of K4-free graphs, arXiv:2506.00414 [math.CO] (31 May 2025)

  4. [12]

    Ghalavand, X

    A. Ghalavand, X. Li, On the local metric dimension of K5-free graphs, submit- ted

  5. [13]

    Harary, R.A

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

  6. [14]

    Jannesari, B

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

  7. [15]

    Javaid, H

    I. Javaid, H. Benish, M. Murtaza, The fractional local metric dimension of graphs, Contrib. Discrete Math. 19 (2024) 163–177

  8. [16]

    Khuller, B

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

  9. [17]

    Klavˇ zar, D

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

  10. [18]

    Klavˇ zar, M

    S. Klavˇ zar, M. Tavakoli, Local metric dimension of graphs: generalized hierar- chical products and some applications, Appl. Math. Comput. 364 (2020) Paper 124676

  11. [19]

    A.N.A. Koam, A. Ahmad, M. Azeem, A. Khalil, M.F. Nadeem, On adjacency metric dimension of some families of graph, J. Funct. Spaces (2022) Paper 6906316

  12. [20]

    Kuziak, I.G

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

  13. [21]

    Lal, V.K

    S. Lal, V.K. Bhat, On the local metric dimension of generalized wheel graph, Asian-Eur. J. Math. 16 (2023) Paper 2350194. 11

  14. [22]

    Okamoto, B

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

  15. [23]

    Rodr ´ ıguez-Vel´ azquez, G.A

    J.A. Rodr ´ ıguez-Vel´ azquez, G.A. Barrag´ an-Ram ´ ırez, C. Garc ´ ıa G´ omez, On the local metric dimension of Corona product graphs, Bull. Malays. Math. Sci. Soc. 39 (2016) S157–S173

  16. [24]

    Slater, Leaves of trees, Congress

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

  17. [25]

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

Pith tools

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