Pith. sign in

REVIEW 5 major objections 3 minor 1 cited by

On the local metric dimension of $K_4$-free graphs

T0 review · 5 major / 3 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 The paper proves that every K4-free graph with at least four vertices has a local resolving set of size at most half its vertices, confirming the omega = 3 case of a conjecture and settling a planar-graph problem.

desk verdict Novel and likely correct bound for K4-free graphs, but the proof rests on asserted structural facts and a hand-waved final step. read the letter →

arxiv 2506.00414 v1 pith:MGWTF7RI submitted 2025-05-31 math.CO

Ali Ghalavand , Sandi Klavžar , Xueliang Li This is my paper
classification math.CO MSC 05C1205C69
keywords localmetricdimensioncliquenumberK4-freegraphplanarresolvingset
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 every graph with at least four vertices and no complete subgraph on four vertices (a $K_4$) has a local resolving set of size at most half its vertices, i.e. $\dim_l(G) \le \lfloor n(G)/2 \rfloor$. This confirms the case $\omega(G)=3$ of a conjecture that a graph with clique number $\omega$ has local metric dimension at most $(\omega-2)/(\omega-1)\,n(G)$. It also gives a positive answer to an open problem about planar graphs from [1], since planar graphs with $\omega(G)\le 3$ are covered. The bound is tight: there are infinitely many planar $K_4$-free graphs whose local metric dimension equals $\lfloor n/2\rfloor$, so the factor $1/2$ cannot be improved for this class. The proof works by partitioning the graph into small induced subgraphs and carefully choosing a large set of vertices that are not needed in a local resolving set.

What carries the argument

The key object is the local vertex division: greedily delete maximum sets of vertex-disjoint induced subgraphs isomorphic to the nine connected non-complete graphs on at most four vertices ($F_1,\dots,F_9$), leaving isolated vertices $F_{10}$. The partition into blocks $F_i(G)$ has structural restrictions coming from $\omega(G)\le3$ and maximality, stated as Facts 1\u20135 and statements I\u2013IV. Using these restrictions, a sequence of fifteen \u2018processes\u2019 adjusts an initially chosen set $S$ of vertices, swapping vertices between $S$ and its complement, until $V(G)-S$ is a local resolving set and $|S|\ge n/2$.

What would settle it

An exhaustive computer check of all connected $K_4$-free graphs of order at most, say, 12, computing $\dim_l(G)$ exactly and comparing with $\lfloor n/2\rfloor$, would settle the theorem's validity over that range; finding one graph with $\dim_l(G)>\lfloor n/2\rfloor$ disproves Theorem 3. The same search can test each of the unproven structural Facts 1\u20135 and statements I\u2013IV by inspecting attachments in a greedy local vertex division.

Watch

Extended reading notes

Core claim

For a graph $G$ with $n(G)\ge 4$ and $\omega(G)\le 3$, the paper constructs a subset $S\subseteq V(G)$ with $|S|\ge n(G)/2$ such that $V(G)-S$ is a local resolving set. Since $\dim_l(G)$ is the minimum size of such a set, the theorem $\dim_l(G)\le \lfloor n(G)/2\rfloor$ follows. This verifies Conjecture 2 from [8] for $\omega(G)=3$. The equality examples are the planar graphs formed from disjoint edges $(n-1)/2\,K_2$ plus one universal vertex; for these graphs $\dim_l(G)=\lfloor n/2\rfloor$, so the constant $1/2$ is best possible. As a corollary, Problem 1 of [1] has a positive answer for planar graphs with clique number at most 3, while it is already known from [9] to fail for planar graphs containing $K_4$.

Load-bearing premise

The proof leans on unproven structural statements, Facts 1\u20135 and statements I\u2013IV in Section 2, which assert exactly how a vertex outside a greedily chosen block can attach to it; if one of these assertions fails for some $K_4$-free graph, the constructed set $S$ may not certify $\dim_l(G)\le n/2$.

Editorial extensions

If this is right

  • Every $K_4$-free graph of order at least 4 has $\dim_l(G)\le \lfloor n(G)/2\rfloor$.
  • Conjecture 2 holds for all graphs with clique number at most 3, and remains open for $4\le \omega(G)\le n(G)-4$.
  • Problem 1 of [1] has a positive answer for planar graphs with $\omega(G)\le3$.
  • The constant $1/2$ is best possible: infinitely many planar $K_4$-free graphs achieve equality.
  • The examples $((n-1)/2)K_2+K_1$ show the bound can be met exactly, not just asymptotically.

Reading between the lines

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

  • A natural testable extension is to run the same greedy local vertex division on graphs with $\omega=4$; the list of small blocks would grow, the structural attachment facts would need re-proving, and a computer search over small graphs could reveal whether the general conjecture's bound $(\omega-2)/(\omega-1)n$ holds there.
  • The unproven structural Facts 1\u20135 and statements I\u2013IV are the most exposed part of the method; a reader who wants to reuse the technique would need those derivations in full, and they are the right target for a revision.
  • The equality construction uses only odd orders, so checking whether even-order $K_4$-free graphs can also attain $\dim_l(G)=n/2$, or whether the bound is rarely sharp, is a concrete open question.
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 / 3 minor

Summary. The paper proves that every K_4-free graph G of order n(G) ≥ 4 satisfies dim_l(G) ≤ floor(n(G)/2). This confirms Conjecture 2 from [8] for clique number 3 and gives a positive answer to Problem 1 from [1] for planar graphs with ω(G) ≤ 3. The proof builds a 'local vertex division' of G into maximum sets of disjoint induced subgraphs drawn from the nine non-complete graphs on at most four vertices with no isolated vertices, then applies a sequence of fifteen processes that update a set S, and finally claims that |S| ≥ n(G)/2 and that V(G)−S is a local resolving set. The paper also exhibits infinitely many planar graphs attaining equality.

Significance. If the proof were correct, the result would be a substantial step in the local metric dimension literature: it settles the omega=3 case of a named conjecture and answers an open problem for a large class of planar graphs, matching the best possible constant 1/2. The construction is concrete and the theorem is falsifiable and easy to test on examples; the claimed extremal family is plausible. The paper also has the virtue of being self-contained in its main line: it does not rely on the conjecture as an input, and no fitted free parameters appear. However, the proof as written delegates several load-bearing steps to assertions that are not derived, and the final verification of both |S| ≥ n/2 and local resolution is one sentence. These gaps are central rather than cosmetic.

major comments (5)
  1. [Section 2, final paragraph] The claim 'It is clear that |S| ≥ n(G)/2' after the fifteenth process is not derived. Each process changes the size of S in a different way: for example, process 13 removes h^1_{i2} and adds h^1_{i3}, f^1_{i1}, f^1_{i2}, while process 12 removes three vertices and adds six, and processes 14 and 15 similarly change the balance. Since S is updated cumulatively across fifteen processes, the paper needs an explicit invariant or a global counting argument showing that at least half of all vertices end up in S. Without that accounting, the main inequality dim_l(G) ≤ floor(n(G)/2) does not follow from the construction.
  2. [Section 2, final paragraph] The statement 'by utilizing ω(G) ≤ 3 and the maximality of F_i(G) for i ∈ [9], we can observe that V(G)−S serves as a local resolving set for G' is the core of the proof, but it is only asserted. The preceding Facts 1–5 and statements I–IV describe how a single outside vertex can attach to one block under maximality; they do not control arbitrary adjacent pairs of vertices outside S after the cumulative swaps, nor do they control distances from V(G)−S when cross-block edges and previously processed triangles are altered. A proof is needed that every adjacent pair in V(G)−S is distinguished by W = V(G)−S, including pairs formed during the processes when vertices move between S and W. This is not a routine verification, since each swap can create new adjacent S-pairs and can change the distance profile of existing W-vertices.
  3. [Section 2, Facts 1–5] Facts 1–5 are introduced with 'the following facts' and are used to justify the initial construction of S, but no derivation is given. They are strong structural statements: for instance, Fact 3 asserts that in a maximum F_4-set no outside vertex can be adjacent to three vertices of H and that the induced subgraph on V(H)∪{v} contains no triangle, and Fact 5 asserts that for F_6, F_7, F_8, F_9 every outside vertex has at most one neighbor in H. These claims depend on the exact ordering of the F_i selections and on the maximality of the earlier families; they need proofs from ω(G) ≤ 3 and the maximality of F_i(G). Without these derivations, the very first construction of S is not justified.
  4. [Section 2, Statements I–IV] Statements I–IV are similarly asserted without proof. They are not local attachment facts of the same type as Facts 1–5; for example, Statement IV involves two distinct triangles F and F′ and one F_2-block and asserts that the union of their neighbor sets in that block has size exactly 1. Statements I and II assert the absence of all edges between certain families. These statements are used explicitly in the processes (e.g., to decide which vertices may be moved into S), so the proof depends on them as heavily as on Facts 1–5. The paper should either prove each statement from the maximality of F_1(G) and F_2(G) or restructure the argument to avoid them.
  5. [Section 2, initial construction of S] After the initial construction of S, the text says 'Since it is evident that S satisfies the required two conditions, the claim is proved.' This is not evident for F_2-blocks: when one puts {b1,b2} into S, the adjacent pair (b1,b2) must be distinguished by a vertex of V(G)−S, but the only remaining paw vertex b3 is not adjacent to b2, and it is not shown whether some outside W-vertex distinguishes b1 and b2. The local resolving property therefore depends on cross-block adjacencies that are never analyzed at this stage. The same issue already appears for F_4 and F_5, where 'two arbitrary non-adjacent vertices' are placed in S. A rigorous proof of the two required conditions for the initial S is needed before the fifteen processes can be meaningfully applied.
minor comments (3)
  1. [Section 2, 3rd process, (3.4)] The condition 'd_H(h) ≤ 2' in step (3.4) is ambiguous because H ∈ F_2(G) is a paw, whose vertices have degrees 1, 2, 2, and 3; it should be stated explicitly which vertex of the paw is meant by h and whether h is the vertex of degree 1 or one of the degree-2 vertices.
  2. [Introduction, equality example] The claim that the graph (n−1)/2 K_2 + K_1 has local metric dimension floor(n/2) is stated as 'straightforward to observe'; since this example is used to show the bound is tight and that infinitely many planar graphs attain equality, a short proof or a reference for this computation would be helpful.
  3. [Throughout Section 2] The notation for the many processes is hard to follow because the same symbols h^1_i, f^1_i, V^9_j, etc. are reused after vertices are removed from the corresponding blocks (e.g., after process 5, V^9_j is decreased but the block is still called F^9_j). A table of the vertex counts and the exact number of vertices remaining in each type of block after each process would substantially improve readability and would also make the missing counting argument easier to supply.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof constructs a local resolving set directly and does not assume the theorem; the main weakness is an asserted final verification, which is a proof gap rather than a circular step.

full rationale

The paper's derivation chain is self-contained. Theorem 3 is proved by explicitly constructing a set S with |S| >= n(G)/2 and then claiming V(G)-S is a local resolving set; this is a direct construction argument, not a reduction to the theorem's conclusion. The self-citations to Conjecture 2 from [8] and the omega=4 counterexample from [9] appear only as motivation and context; neither is used as a premise in the proof of Theorem 3. No parameter is fitted to data, no external uniqueness theorem is imported, and no known result is renamed as a new one. The genuine weakness is rigor: the final sentence 'It is clear that |S| >= n(G)/2. Furthermore, by utilizing omega(G) <= 3 and the maximality of Fi(G) for i in [9], we can observe that V(G)-S serves as a local resolving set for G' asserts the two properties that carry the theorem, and the structural Facts 1-5 and I-IV are stated without derivation. However, an unsupported assertion is not circular equivalence: the claimed conclusion is not identical to an input, nor is it forced by a self-citation chain. The gap would be a correctness or completeness concern, not a circularity concern. Therefore the circularity score is 0.

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

No free parameters or invented entities. The proof rests on a greedy decomposition into nine small graph types and a lengthy process sequence; the robustness of that construction is assumed rather than demonstrated, so the load-bearing unproven statements are recorded as axioms.

assumptions (4)
  • standard math G is a simple connected graph and all standard metric dimension definitions apply.
    The introduction states that G is a simple connected graph; the proof uses standard distance, resolving set, and local resolving set definitions.
  • ad hoc to paper Facts 1-5 about local vertex division attachment patterns hold as stated.
    Asserted after the local vertex division definition in Section 2 without proof; these facts are load-bearing for the construction of S.
  • ad hoc to paper Statements I-IV about triangles in F3(G) hold.
    Asserted in Section 2 and used to justify the first and second processes; no proof is supplied.
  • ad hoc to paper The final counting and local-resolution verification for the set S is valid.
    The paper says 'It is clear that |S| >= n(G)/2' and 'we can observe that V(G)-S is a local resolving set'; the detailed verification is not given.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the local metric dimension of $K_4$-free graphs." pith.science (2026). https://pith.science/paper/MGWTF7RI

@misc{pith2026250600414,
  author       = {Pith},
  title        = {Pith review of: On the local metric dimension of $K_4$-free graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MGWTF7RI}},
  note         = {Machine review of arXiv:2506.00414}
}
abstract

Let $G$ be a graph of order $ n(G) $, local metric dimension $ \dim_l(G) $, and clique number $ \omega(G) $. It has been conjectured that if $ n(G) \geq \omega(G) + 1 \geq 4 $, then $ \dim_l(G) \leq \left( \frac{\omega(G) - 2}{\omega(G) - 1} \right) n(G) $. In this paper the conjecture is confirmed for the case $ \omega(G) = 3 $. Consequently, a problem regarding the local metric dimension of planar graphs is also resolved.

Figures

Figures reproduced from arXiv: 2506.00414 by the authors.

Figure 1
Figure 1. Let now G be a graph with n(G) ≥ 4 > ω(G). In the following, we will se￾quentially select in G and in its induced subgraphs maximum sets of vertex disjoint 3 [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 1
Figure 1. All non-complete graphs with at most 4 vertices and no isolated vertex. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

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

    math.CO 2025-07 conditional novelty 6.0 of 10

    For every non-complete connected graph with clique number at least 3, the local adjacency metric dimension is at most floor(((ω−2)/(ω−1)) n), confirming the long-open conjecture for the local metric dimension.

Reference graph

Works this paper leans on

20 extracted references · 3 canonical work pages · cited by 1 Pith paper

  1. [8]

    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

    2023

  2. [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

    2022

  3. [9]

    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)

    arXiv 2024

  4. [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

    2019

  5. [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

    2016

  6. [4]

    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

    2017

  7. [5]

    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

    2018

  8. [6]

    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. 13

    work page 2014

Show all 20 references
  1. [7]

    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

    2024

  2. [10]

    Harary, R.A

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

    1976

  3. [11]

    Javaid, H

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

    2024

  4. [12]

    Khuller, B

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

    1996

  5. [13]

    Klavˇ zar, D

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

    2023

  6. [14]

    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

    2020

  7. [15]

    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)

    2021 arXiv

  8. [16]

    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

    2023

  9. [17]

    Okamoto, B

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

    2010

  10. [18]

    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

    2016

  11. [19]

    Slater, Leaves of trees, Congress

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

    1975

  12. [20]

    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. 14

    2023

Pith tools

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