REVIEW 2 major objections 4 minor 15 references
Mixed metric dimension of $2$-connected graphs
T0 review · 2 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash
Pith's one-line read This paper proves that every 2-connected graph that is not a cycle has mixed metric dimension at most 2c(G), the double of its cyclomatic number, and derives a proof of the conjecture from [12] for all connected non-cycle graphs.
desk verdict Resolves the last open case of the Sedlar–Škrekovski conjecture with a simple 2c(G) bound; the proof is sound except for one outsourced theta-graph base case that needs checking. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central device is the thread and the midpoint-plus-endpoint augmentation. A thread is a path whose internal vertices all have degree 2; a maximal thread runs between two branch vertices. Lemma 2.4 is the workhorse: if H is obtained from G by deleting the internal vertices of a thread P whose endpoints are at least as far apart in H as P is long, then dim_m(G) ≤ dim_m(H) + 2, witnessed by adding one endpoint u and the midpoint w of P. Lemmas 2.1 and 2.2 convert a failure of the short-thread condition into a short u–v path in G − P⁰, forcing the branch set B to generate the mixed metric dimension. The identity c(G) = c(H) + 1 for a removed maximal thread drives the induction.
What would settle it
Compute the mixed metric dimension of every graph formed by three internally disjoint paths joining two branch vertices—that is, every 2-connected graph with c(G) = 2. If any such graph has dim_m(G) ≥ 5, Theorem 1.2 is false; verifying that all have dim_m(G) ≤ 4 would confirm the sole external base case.
Extended reading notes
Core claim
On the paper's own terms, the core discovery is Theorem 1.2: for a 2-connected graph G that is not a cycle, dim_m(G) ≤ 2c(G). The proof decomposes G into maximal threads—paths whose internal vertices all have degree 2—and then splits into two regimes. If every thread is short, the branch vertices (degree at least 3) already form a mixed metric generator of size at most 2c(G) − 2. If some maximal thread is not short, deleting its internal vertices yields a smaller graph H with c(H) = c(G) − 1, and Lemma 2.4 shows that adding one endpoint and the thread's midpoint to a generator of H produces a generator of G. Induction on the cyclomatic number finishes the argument. Combining this with previo
Load-bearing premise
The induction's base case, c(G) = 2, is outsourced to two corollaries from [11] that are not restated; the whole theorem stands only if those corollaries really cover every 2-connected graph with cyclomatic number 2 that is not a cycle.
Editorial extensions
If this is right
- Conjecture 1.1 becomes a theorem: every connected graph that is not a cycle has dim_m(G) ≤ ℓ(G) + 2c(G).
- For leafless 2-connected graphs in which every maximal thread is short, the branch vertices alone form a mixed metric generator of size at most 2c(G) − 2.
- The proof yields a recursive construction of a mixed metric generator of size at most 2c(G) by repeatedly stripping non-short maximal threads and adding two landmarks per stripped thread.
- The bound grows only linearly with the cyclomatic number, so graphs with few independent cycles have small mixed metric dimension regardless of their size.
- Together with Theorems 3.1–3.3, the theorem covers every connected non-cycle graph, so the conjecture no longer requires separate treatment for any remaining class.
Reading between the lines
- A natural testable strengthening is that the upper bound may be 2c(G) − 2 whenever every maximal thread is short, since the paper's Lemma 2.5 already gives |B| ≤ 2c(G) − 2; the paper only states the weaker 2c(G) bound.
- Because a mixed metric generator simultaneously distinguishes vertices and edges, the same 2c(G) upper bound transfers to the ordinary metric dimension and the edge metric dimension for 2-connected non-cycle graphs, though the paper does not state this transfer.
- The structural proof suggests that exact mixed metric dimension for graphs of bounded cyclomatic number may be computable by fixed-parameter algorithms parameterized by c(G), a direction the paper does not explore.
- The external base case for c(G) = 2 could be replaced by a direct verification of all theta graphs—three internally disjoint paths between two branch vertices—which would make the induction fully self-contained.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the mixed metric dimension of 2-connected graphs. It proves two lemmas: Lemma 2.4, which extends a mixed metric generator of G−P0 to G by adding at most two vertices when a thread is not short, and Lemma 2.5, which shows that the set B of branch vertices is a mixed metric generator when every thread is short. These are combined in Theorem 1.2, stating that every 2-connected non-cycle graph G satisfies dim_m(G) ≤ 2c(G). Together with cited results for trees, graphs with leaves, and leafless graphs with a cut vertex, the paper concludes Sedlar–Škrekovski's Conjecture 1.1 for all connected non-cycle graphs. The internal lemmas are mostly argued in detail, but the proof of Theorem 1.2 has two load-bearing gaps: the handling of length-1 maximal threads and the outsourced base case for theta graphs.
Significance. If Theorem 1.2 is correct, it is a substantial result: it would settle an open conjecture in mixed metric dimension and give a clean linear bound in the cyclomatic number. The paper's elementary approach, especially the branch-vertex generator lemma and the +2 extension lemma, is a promising contribution. The manuscript also gives credit to prior partial results and does not rely on circular reasoning. However, the current proof is incomplete in ways that affect the induction itself, so the significance cannot be fully assessed until the gaps are repaired.
major comments (2)
- [Section 3, proof of Theorem 1.2, Eq. (9)] The reduction to H=G−P0 assumes that removing the internal vertices of a thread P=(p0,...,pl) removes l−1 vertices and l edges. This fails when l=1: a length-1 thread has no internal vertices, so H=G, |E(H)|=|E(G)|, |V(H)|=|V(G)|, and c(H)=c(G), not c(G)−1. Such threads are not covered by the 'short thread' case either, because for l=1 the short condition l<d_H(u,v) is false whenever d_H(u,v)=1. Concretely, in K4 every edge is a maximal thread of length 1 and is non-short; the proof then chooses such a P, obtains H=G, and the induction hypothesis is applied to a graph with the same cyclomatic number. Thus the proof as written does not cover complete graphs and, more generally, graphs whose only maximal threads have length 1. Please add a separate argument for this case, or restrict the reduction to threads with l≥2 and prove that such a thread exists whenever the all-short case does not
- [Section 3, proof of Theorem 1.2, base case c(G)=2] The case in which H=G−P0 is a cycle is settled by the statement 'It follows from [11, Corollaries 8 and 11]' without restating those results. This is the induction base: for c(G)≥3 the proof invokes the theorem for H with c(H)=c(G)−1, so the induction is sound only if the cited corollaries prove the needed bound dim_m(G)≤4 for every theta graph — all three internally disjoint paths between the two branch vertices, including paths of length 1 and 2. The manuscript neither states the corollaries nor explains how they cover this full class and provide exactly the required bound. Please restate the corollaries and verify their coverage, or give a self-contained proof of this base case. Without this, the induction has no verified base.
minor comments (4)
- [Section 2, Lemma 2.2] In the proof, 'Take now a shortest path from u to u' and a shortest path from v to u'' should presumably read '... from v to v''; otherwise the concatenation argument in the u'≠v' case does not follow from the stated paths.
- [Section 2, Lemma 2.4] Claim 2's proof splits into l even and l=2k+1≥3 but does not address l=1. For l=1 the set O(P)\O(H) is empty, so the claim is vacuous; this should be stated explicitly to avoid a gap in the proof structure.
- [Section 2, Lemma 2.5, Case 3] When w is a vertex, the proof says Lemma 2.1 implies d_{G−P0}(u,v)≤l without spelling out that Lemma 2.1 is applied twice, once for the u–w pair and once for the v–w pair, and that the two shortest paths are concatenated at w. Please make this implicit step explicit.
- [Throughout] There are several small typos, e.g., 'opposite sides side of w' in Lemma 2.4 and 'The authors showed' in the introduction; these should be corrected in a final polishing pass.
Circularity Check
No circularity: the proof is an induction whose base cases and non-2-connected cases cite external prior work, not the present conjecture or the authors' own results.
full rationale
No circular step is present. The internal lemmas are independent of the target theorem: Lemma 2.4 proves dim_m(G) <= dim_m(H) + 2 under an explicit length condition l >= d_H(u,v), and Lemma 2.5 proves that B is a mixed metric generator when every thread is short; neither lemma assumes the inequality dim_m(G) <= 2c(G). The proof of Theorem 1.2 then splits into cases: if every thread is short, Lemmas 2.3 and 2.5 give the bound directly; otherwise it removes a maximal thread P and analyzes H = G - P0. If H is a cycle, the c(G)=2 base case is cited from [11, Corollaries 8 and 11], which are external published results by Sedlar and Skrekovski, not by the present authors. If H has a cut-vertex, the proof invokes [2, Corollary 12(i)], again an external result. If H is 2-connected, the proof applies a genuine induction on c(G), since c(H) = c(G)-1; this reduces to smaller instances, not to the same claim. The use of an external base case is a verification/completeness concern: the paper does not restate the two corollaries or explicitly confirm they cover all theta graphs with the required bound, so a failure there would leave a gap in the induction. However, that is an unverified external dependency, not a self-referential or definitional reduction, and it does not qualify as circularity under the stated rules.
Assumptions & free parameters
assumptions (6)
- standard math Finite, simple, connected graph with standard distance d_G
- domain assumption Whitney-type decomposition into maximal threads
- domain assumption Theorem 3.1 = [2, Cor. 16]: ℓ(G)≥1 non-tree ⇒ dim_m(G) ≤ ℓ(G)+2c(G)
- domain assumption Theorem 3.2 = [6, Thm 4.3]: tree ⇒ dim_m(G)=ℓ(G)
- domain assumption Theorem 3.3 = [2, Cor. 12(i)]: ℓ=0 and cut-vertex ⇒ dim_m(G)≤2c(G)
- domain assumption [11, Corollaries 8 and 11]: c(G)=2 cycle-plus-thread graphs satisfy dim_m(G)≤2c(G)
Cite this review
Pith. "Pith review of Mixed metric dimension of $2$-connected graphs." pith.science (2026). https://pith.science/paper/VGRCPGBO
@misc{pith2026260727573,
author = {Pith},
title = {Pith review of: Mixed metric dimension of $2$-connected graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/VGRCPGBO}},
note = {Machine review of arXiv:2607.27573}
}
abstract
We show that for a $2$-connected graph $G$ which is not a cycle, the mixed metric dimension of $G$ is at most $2c(G)$, where $c(G)$ is cyclomatic number of $G$. As an immediate application, we prove a conjecture proposed by Sedlar and \v{S}krekovski.
Reference graph
Works this paper leans on
-
[1]
C´ aceres, C
J. C´ aceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, D. R. Wood, On the metric dimension of cartesian product of graphs,SIAM J. Discrete Math.21(2007) 423–441
2007
-
[2]
Chakraborty, F
D. Chakraborty, F. Foucaud, A. Hakanen, Distance-based (and path-based) cov- ering problems for graphs of given cyclomatic number,Discrete Math.348(2025) 114595
2025
-
[3]
Chartrand, C
G. Chartrand, C. Poisson, P. Zhang, Resolvability and the upper dimension of graphs,Comput. Math. Appl.39(2000) 19–28
2000
-
[4]
Harary, R
F. Harary, R. A. Melter, On the metric dimension of a graph,Ars Combin.2 (1976) 191–195
1976
-
[5]
H. Hua, Y. Chen, X. Hua, Further results on the mixed metric dimension of graphs,Discrete Appl. Math.367(2025) 99–106
2025
-
[6]
Kelenc, D
A. Kelenc, D. Kuziak, A. Taranenko, I. G. Yero, Mixed metric dimension of graphs,Appl. Math. Comput.314(2017) 429–438
2017
-
[7]
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
-
[8]
Khuller, B
S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs,Discret. Appl Math.70(1996) 217–229
1996
Show all 15 references
-
[9]
Kuziak, I
D. Kuziak, I. G. Yero, Metric dimension related parameters in graphs: a survey on combinatorial, computational and applied results, arXiv: 2107.04877, 2021
2021 arXiv
-
[10]
R. A. Melter, I. Tomescu, Metric bases in digital geometry,Comput. Vis. Gr. Image Process.25(1984) 113–121
1984
-
[11]
Sedlar, R
J. Sedlar, R. ˇSkrekovski, Extremal mixed metric dimension with respect to the cyclomatic number,Appl. Math. Comput.404(2021) 126238
2021
-
[12]
Sedlar, R
J. Sedlar, R. ˇSkrekovski, Mixed metric dimension of graphs with edge disjoint cycles,Discrete Appl. Math.300(2021) 1–8. 10
2021
-
[13]
P. J. Slater, Leaves of trees,Congr. Numer.14(1975) 549–559
1975
-
[14]
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
2023
-
[15]
Whitney, Non-separable and planar graphs,Trans
H. Whitney, Non-separable and planar graphs,Trans. Amer. Math. Soc.34 (1932) 339–362. 11
1932
Reviewed August 1, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.