Pith. sign in

REVIEW 2 major objections 4 minor 77 references

A single breadth-first-search edge-selection scheme gives near-tight upper bounds, linear in the cyclomatic number and leaf count, for many distance-based covering problems, and proves the open conjecture that every connected graph has a di

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

For every connected graph, the distance-edge-monitoring number is at most the cyclomatic number plus one, and similar linear bounds hold for metric dimension, geodetic number, and isometric path covers.

T0 review reviewed 2026-08-05 challenge →

load-bearing objection Solid, genuinely useful paper that resolves a real conjecture, but the flagship proof of Theorem 20 has a false inference that needs a two-case patch before the result is rigorous. the 2 major comments →

arxiv 2509.00383 v1 pith:FW66QTWF submitted 2025-08-30 cs.DM math.CO

Distance-based (and path-based) covering problems for graphs of given cyclomatic number

Dibyayan Chakraborty , Florent Foucaud , Anni Hakanen This is my paper
classification cs.DM math.CO MSC 05C1205C8568Q25
keywords cyclomatic numberfeedback edge setmetric dimensionmixed metric dimensiongeodetic setdistance-edge-monitoring setisometric path coverbreadth-first search
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

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 tries to establish that one simple breadth-first-search construction controls many hard distance-covering problems on graphs with few cycles. The construction picks a feedback edge set by keeping all horizontal edges and, at each vertex, dropping one upward edge; removing those edges leaves a tree whose root-to-leaf paths are isometric. The authors show that the root and the endpoints of the dropped edges, plus leaves or extra endpoints depending on the problem, form small solutions for metric dimension variants, geodetic sets, monitoring sets, and isometric path covers. The headline result is that every connected graph has a distance-edge-monitoring set of size at most c(G)+1, resolving Conjecture 4, and the other bounds are close to tight and lead to polynomial-time algorithms for graphs of bounded cyclomatic number.

Core claim

The paper shows that a good edge set — a feedback edge set obtained from a breadth-first search: all edges whose endpoints are equidistant from the root, plus, at each vertex, all but one of the edges leading one level closer to the root — is a universal building block. Removing such a set leaves a tree, and every root-to-leaf path in that tree is a shortest path in the original graph. Taking the root, the endpoints of the good edge set, and (where needed) the leaves gives small resolving sets, edge- and mixed resolving sets, geodetic sets, monitoring edge-geodetic sets, distance-edge-monitoring sets, and isometric path covers or partitions. Concretely, the paper proves dem(G) ≤ c(G)+1; dim(

What carries the argument

The central object is a good edge set with respect to a breadth-first-search root r: a set F containing every horizontal edge (both endpoints at the same BFS level) and, for each vertex u ≠ r, exactly |Br(u)|−1 of the edges from u to the previous level. Removing F produces a tree T_F whose root-to-leaf paths are isometric in G, and F is automatically a minimum feedback edge set. The paper builds candidate solutions by selecting vertices on or near these edges; the isometric-path property of T_F is what makes distances along the tree predictable, so one construction works across many different covering problems.

Load-bearing premise

The metric-dimension bounds inherit an unproved quoted theorem saying the BFS-endpoint set resolves all pairs; and the distance-edge-monitoring proof (Section 4.3) uses the claim that any edge left out of the feedback set is the sole upward edge at its far endpoint, a property that does not follow from the definition of a good edge set.

What would settle it

Fix a connected graph with minimum degree 2 and cyclomatic number at least 3, choose a BFS root r, and construct a good edge set F. Look for a vertex u with two neighbors one level closer to r, where F keeps one of those two edges and omits the other e. The proof of Theorem 20 asserts this cannot happen; when it does happen, check whether every isometric path from u to r still passes through e. A single such graph whose omitted edge is not monitored by the constructed set would refute the proof of dem(G) ≤ c(G)+1; if none exists, the bound may survive but needs a different argument.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Conjecture 4 is settled: every connected graph has a distance-edge-monitoring set of size at most c(G)+1.
  • Metric and edge metric dimension are bounded by L(G)+2c(G)+1 for every graph, and the conjectured L(G)+2c(G) bound holds whenever L(G) ≥ 1; mixed metric dimension obeys the conjectured ℓ(G)+2c(G) bound when leaves exist.
  • The monitoring edge-geodetic bound drops from 9c+ℓ−8 to 3c+ℓ+1, and to 3c+ℓ when a cut-vertex exists, matching the known extremal construction up to an additive 1.
  • Isometric path edge-covers and partitions fit the same framework, with bounds 3c+⌈(ℓ+1)/2⌉ and 2c+ℓ, both nearly tight.
  • All constructions run in linear time and give polynomial-time (n^{O(c)}) algorithms for graphs of bounded cyclomatic number, even though several of these problems are NP-hard on bounded treewidth.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The good-edge-set method is probably not limited to the problems listed here; the paper itself suggests geodesic-transversal sets as a natural next target, and similar linear-in-c bounds may hold for other distance-based invariants on nearly acyclic graphs.
  • If the gap in the proof of Theorem 20 can be repaired, the dem bound is tight, since the paper cites extremal graphs with dem(G)=c(G)+1; a direct test is to search for graphs where an omitted upward edge is not forced through by the constructed set.
  • The XP algorithms for vertex-subset problems might be upgraded to FPT for the feedback-edge-set parameter if the additive constants can be kernelized; the path-cover problems would require a different argument because solutions are collections of paths rather than vertex subsets.
  • The paper's own closing remark on strong metric dimension draws a boundary: parameters needing half the vertices of a cycle cannot obey any linear-in-c bound, so the technique applies exactly where shortest-path structure remains tree-like.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper develops a unified breadth-first-search technique, based on 'good edge sets', for bounding distance-based and path-based covering parameters on connected graphs in terms of the cyclomatic number c(G) and the number of leaves ℓ(G). It applies the technique to metric dimension, edge and mixed metric dimension, geodetic sets, monitoring edge-geodetic sets, distance-edge-monitoring sets, and isometric path covers/partitions. The main claims are explicit linear-time constructible upper bounds, resolution of Conjecture 4 (dem(G) ≤ c(G)+1), partial resolutions/improvements of Conjectures 1–3, and XP algorithms for computing optimal values on graphs of bounded cyclomatic number.

Significance. If the proofs are completed, this is a substantial contribution: it unifies and improves several recent lines of work, gives bounds that match known lower-bound constructions in several cases, and resolves a stated conjecture. The method is constructive and the paper is transparent about relying on external results (notably Theorem 8 of Lu et al. for doubly resolving sets). The algorithmic consequences, while not the main focus, are a useful bonus. The good-edge-set technique is clearly explained and appears to be a genuinely versatile tool for this family of problems.

major comments (2)
  1. [§4.3, Theorem 20] The proof contains the assertion 'Since e is not in F, we have |Br(u)| = 1.' This is false. Goodness of F only gives |Br(u)∩F| = |Br(u)| − 1. If |Br(u)| = 1, then the unique edge is indeed outside F, but if |Br(u)| ≥ 2, the edge e may simply be the single non-F edge in Br(u). The subsequent monitoring argument therefore omits the case |Br(u)| ≥ 2. The statement is likely salvageable: if |Br(u)| = 1, then r ∈ S monitors e via the pair (r,u); if |Br(u)| ≥ 2, then Br(u) contains at least one F-edge, so u (the farthest endpoint of that vertical F-edge) lies in S, and e is monitored by (u,v). Since Theorem 20 is the paper's resolution of Conjecture 4, the proof must be corrected.
  2. [§3, Proposition 9] The proof states that the isometric paths P'_e and P'_f are internally vertex-disjoint, 'since otherwise the vertex after which the paths diverge is an element of S'. This does not follow from goodness of F. If the two paths share a prefix and diverge at a vertex z, goodness only forces at least one of the two downward edges from z to be in F, so one of the two next vertices (not z itself) is in S. The argument then also uses 'sve, svf ∈ Br(s)' as though these were two distinct edges, which fails when the shared prefix has length at least one. Since Proposition 9 is load-bearing for the edge-metric-dimension bounds of Corollary 12, this proof gap must be repaired. The claim may be true, but the written reasoning needs a case distinction (e.g., taking the last common vertex of the two paths).
minor comments (4)
  1. [§4.3, Theorem 20] The sentence 'S is thus a monitoring edge-geodetic set' should read 'distance-edge-monitoring set', since the definition just given is the distance-edge-monitoring one (one endpoint in S, the other arbitrary).
  2. [Corollary 16] The displayed conclusion is duplicated: the three inequalities are printed twice in the same line. Please remove the duplicate.
  3. [§4.1, Theorem 17] The assertion 'Due to Lemma 6, L ∪ {r} is a geodetic set of G' is stated without proof. It is true because paths in the BFS tree TF are isometric in G, but a one-sentence justification would help the reader.
  4. [§1, Introduction] Typo: 'use with sucess' should be 'use with success'.

Circularity Check

0 steps flagged

No circularity; the bounds are constructive and no target value is fitted or self-defined. The only flagged issue is a false inference in Theorem 20's proof, which is a correctness gap rather than a circularity.

full rationale

The derivation chain is self-contained for circularity purposes. All upper bounds are obtained by explicit constructions: one computes a good edge set F w.r.t. a BFS root r (Lemma 5), with |F| = c(G) proven by Lemma 6 and Observation 7, and then counts the size of the constructed vertex set or path family. No conjecture is assumed as input, no parameter is fitted to the quantity being bounded, and no known result is merely renamed. The engine, Theorem 8 of Lu-Ye-Zhu [53], is an external published result with independent proof, so the Section 3 bounds are conditional on an external theorem, not circular. Self-citations ([30,31,33]) are normal because those papers posed the conjectures; proving them is not circular. However, per the review rule, one missing support should be flagged explicitly: in Theorem 20 (Section 4.3), the proof states 'Since e is not in F, we have |Br(u)| = 1.' This does not follow from goodness (|Br(u) ∩ F| = |Br(u)|-1), so the written proof of the dem bound is incomplete for vertical non-F edges with |Br(u)| >= 2. This is a correctness/rigor gap, not a circularity: the claimed bound c(G)+1 is not defined in terms of itself, not derived from the conjecture, and a two-case repair appears to restore the argument. It therefore does not raise the circularity score, which remains 1.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The paper proves its key structural lemmas (good edge sets, Lemma 6) but imports three prior results as black boxes: Theorem 8 of [53], Lemma 19 of [30], and Propositions 13-14 of [42,43,45]. These are external, independently published results, not fitted or assumed to include the target bounds.

axioms (3)
  • domain assumption Theorem 8 of [53]: for a connected graph G with δ(G)≥2 and root r, the set S = {r} ∪ endpoints of a good edge set is a doubly resolving set; if r is a cut-vertex, S\{r} still is.
    Used as the engine for all metric-dimension bounds in Section 3 (Corollaries 12 and 16). Proof is in the cited paper, not reproduced here.
  • domain assumption Lemma 19 of [30]: any distance-edge-monitoring set of the base graph Gb is also a distance-edge-monitoring set of G.
    Used in Theorem 20 to reduce to minimum degree at least 2.
  • domain assumption Propositions 13 and 14 from [42] and [43,45]: for a tree T, the leaves form a mixed metric basis; a branch-resolving set is a resolving and edge resolving set.
    Used in Theorem 15 to handle tree parts attached to the base graph.

reviewed 2026-08-05 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Distance-based (and path-based) covering problems for graphs of given cyclomatic number." pith.science (2026). https://pith.science/paper/FW66QTWF

@misc{pith2026250900383,
  author       = {Pith},
  title        = {Pith review of: Distance-based (and path-based) covering problems for graphs of given cyclomatic number},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FW66QTWF}},
  note         = {Machine review of arXiv:2509.00383}
}
Share X Bluesky LinkedIn Reddit HN
abstract

We study a large family of graph covering problems, whose definitions rely on distances, for graphs of bounded cyclomatic number (that is, the minimum number of edges that need to be removed from the graph to destroy all cycles). These problems include (but are not restricted to) three families of problems: (i) variants of metric dimension, where one wants to choose a small set $S$ of vertices of the graph such that every vertex is uniquely determined by its ordered vector of distances to the vertices of $S$; (ii) variants of geodetic sets, where one wants to select a small set $S$ of vertices such that any vertex lies on some shortest path between two vertices of $S$; (iii) variants of path covers, where one wants to select a small set of paths such that every vertex or edge belongs to one of the paths. We generalize and/or improve previous results in the area which show that the optimal values for these problems can be upper-bounded by a linear function of the cyclomatic number and the degree~1-vertices of the graph. To this end, we develop and enhance a technique recently introduced in [C. Lu, Q. Ye, C. Zhu. Algorithmic aspect on the minimum (weighted) doubly resolving set problem of graphs, Journal of Combinatorial Optimization 44:2029--2039, 2022] and give near-optimal bounds in several cases. This solves (in some cases fully, in some cases partially) some conjectures and open questions from the literature. The method, based on breadth-first search, is of algorithmic nature and thus, all the constructions can be computed in linear time. Our results also imply an algorithmic consequence for the computation of the optimal solutions: for some of the problems, they can be computed in polynomial time for graphs of bounded cyclomatic number.

Figures

Figures reproduced from arXiv: 2509.00383 by Anni Hakanen, Dibyayan Chakraborty, Florent Foucaud.

Figure 1
Figure 1. Figure 1: Relations between the graph parameters discussed in the paper. If a parameter [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Vertices in the same horizontal line are equidistant from the root r. The edges drawn in red indicate a set of good edges, and these edges form a feedback edge set. Hence, a tree is obtained by removing the red edges from the given graph. Algorithmic applications. For all the considered problems, our method in fact implies that the optimal solutions can be computed in polynomial time for graphs with bounde… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

77 extracted references · 74 canonical work pages · 3 internal anchors

  1. [1]

    Alcon, M

    L. Alcon, M. Gutierrez, C. Hernando, M. Mora, and I. M. Pelayo. The neighbor-locating-chromatic number of trees and unicyclic graphs. Discussiones Mathematicae Graph Theory, 43(3):659–675, 2023

    work page 2023

  2. [2]

    Andreatta and F

    G. Andreatta and F. Mason. Path covering problems and testing of printed circuits. Discrete Applied Mathematics, 62(1):5–13, 1995

    work page 1995

  3. [3]

    Arokiaraj, S

    A. Arokiaraj, S. Klavˇ zar, P. D. Manuel, E. Thomas, and A. Xavier. Strong geodetic problems in networks. Discussiones Mathematicae Graph Theory, 40(1):307–321, 2020. 13

    work page 2020

  4. [4]

    M. Atici. On the edge geodetic number of a graph. International Journal of Computer Mathematics, 80(7):853–861, 2003

    work page 2003

  5. [5]

    Banik, M

    A. Banik, M. J. Katz, E. Packer, and M. Simakov. Tracking paths. Discrete Applied Mathematics, 282:22–34, 2020

    work page 2020

  6. [6]

    C. Berge. Graphs and Hypergraphs. North-Holland Publishing Company, 1973

    work page 1973

  7. [7]

    C. Berge. Path partitions in directed graphs. In North-Holland Mathematics Studies, volume 75, pages 59–63. Elsevier, 1983

    work page 1983

  8. [8]

    Bergougnoux, O

    B. Bergougnoux, O. Defrain, and F. McInerney. Enumerating minimal solution sets for metric graph problems. Algorithmica, 2025

    work page 2025

  9. [9]

    Bil` o, G

    D. Bil` o, G. Colli, L. Forlizzi, and S. Leucci. On the inapproximability of finding minimum monitoring edge-geodetic sets, 2024

    work page 2024

  10. [10]

    Metric dimension on sparse graphs and its applications to zero forcing sets

    N. Bousquet, Q. Deschamps, A. Parreau, and I. M. Pelayo. Metric dimension on sparse graphs and its applications to zero forcing sets. arXiv eprint, 2021. https://arxiv.org/abs/2111.07845

    work page internal anchor Pith review Pith/arXiv arXiv 2021

  11. [11]

    C´ aceres, M

    M. C´ aceres, M. Cairo, B. Mumey, R. Rizzi, and A. I. Tomescu. Sparsifying, shrinking and splicing for minimum path cover in parameterized linear time. In Proceedings of SODA 2022, pages 359–376. SIAM, 2022

    work page 2022

  12. [12]

    Chakraborty, J

    D. Chakraborty, J. Chalopin, F. Foucaud, and Y. Vax` es. Isometric path complexity of graphs. In J. Leroux, S. Lombardy, and D. Peleg, editors, 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, August 28 to September 1, 2023, Bordeaux, France, volume 272 of LIPIcs, pages 32:1–32:14. Schloss Dagstuhl - Leibniz-Zentrum...

    work page 2023

  13. [13]

    Chakraborty, A

    D. Chakraborty, A. Dailly, S. Das, F. Foucaud, H. Gahlawat, and S. K. Ghosh. Complexity and algorithms for isometric path cover on chordal graphs and beyond. In Proceedings of ISAAC 2022, volume 248 of LIPIcs, pages 12:1–12:17, 2022

    work page 2022

  14. [14]

    Chakraborty, F

    D. Chakraborty, F. Foucaud, and A. Hakanen. Distance-based covering problems for graphs of given cyclomatic number. In H. Fernau and K. Jansen, editors, Fundamentals of Computation Theory - 24th International Symposium, FCT 2023, Trier, Germany, September 18-21, 2023, Proceedings, volume 14292 of Lecture Notes in Computer Science, pages 132–146. Springer, 2023

    work page 2023

  15. [15]

    Chartrand, L

    G. Chartrand, L. Eroh, M. A. Johnson, and O. Oellermann. Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics, 105(1-3):99–113, 2000

    work page 2000

  16. [16]

    Choudhary

    P. Choudhary. Polynomial time algorithms for tracking path problems. Algorithmica, 84(6):1548– 1570, 2022

    work page 2022

  17. [17]

    Coppersmith and U

    D. Coppersmith and U. Vishkin. Solving NP-hard problems in ‘almost trees’: Vertex cover. Discrete Applied Mathematics, 10(1):27–45, 1985

    work page 1985

  18. [18]

    Courcelle

    B. Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Infor- mation and Computation, 85(1):12–75, 1990

    work page 1990

  19. [19]

    E. D. Demaine, D. Eppstein, A. Hesterberg, K. Jain, A. Lubiw, R. Uehara, and Y. Uno. Reconfiguring undirected paths. In Z. Friggstad, J. Sack, and M. R. Salavatipour, editors, Algorithms and Data Structures - 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings, volume 11646 of Lecture Notes in Computer Science, pag...

    work page 2019

  20. [20]

    S. R. Dev, S. Dey, F. Foucaud, N. Krishna, and L. R. Sulochana. Monitoring edge-geodetic sets in graphs. arXiv eprint, 2023. https://arxiv.org/abs/2210.03774

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  21. [21]

    Dumas, F

    M. Dumas, F. Foucaud, A. Perez, and I. Todinca. On graphs coverable by k shortest paths. SIAM Journal on Discrete Mathematics, 38(2):1840–1862, 2024

    work page 2024

  22. [22]

    Eppstein

    D. Eppstein. Metric dimension parameterized by max leaf number. Journal of Graph Algorithms and Applications, 19(1):313–323, 2015. 14

    work page 2015

  23. [23]

    Eppstein, M

    D. Eppstein, M. T. Goodrich, J. A. Liu, and P. Matias. Tracking paths in planar graphs. In P. Lu and G. Zhang, editors, 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China, volume 149 of LIPIcs, pages 54:1–54:17. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur ...

    work page 2019

  24. [24]

    Epstein, A

    L. Epstein, A. Levin, and G. J. Woeginger. The (weighted) metric dimension of graphs: Hard and easy cases. Algorithmica, 72(4):1130–1171, 2015

    2015

  25. [25]

    Fernau, F

    H. Fernau, F. Foucaud, K. Mann, U. Padariya, and K. N. R. Rao. Parameterizing path partitions. Theor. Comput. Sci., 1028:115029, 2025

    work page 2025

  26. [26]

    Fiala, T

    J. Fiala, T. Kloks, and J. Kratochv ´ ıl. Fixed-parameter complexity of λ-labelings. Discrete Applied Mathematics, 113(1):59–72, 2001. Selected Papers: 12th Workshop on Graph-Theoretic Concepts in Computer Science

    work page 2001

  27. [27]

    D. C. Fisher and S. L. Fitzpatrick. The isometric number of a graph. Journal of Combinatorial Mathematics and Combinatorial Computing, 38(1):97–110, 2001

    work page 2001

  28. [28]

    Foucaud, E

    F. Foucaud, E. Galby, L. Khazaliya, S. Li, F. M. Inerney, R. Sharma, and P. Tale. Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover. In 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, volume to appear of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2024

    work page 2024

  29. [29]

    Foucaud, E

    F. Foucaud, E. Galby, L. Khazaliya, S. Li, F. M. Inerney, R. Sharma, and P. Tale. Metric dimension and geodetic set parameterized by vertex cover. In O. Beyersdorff, M. Pilipczuk, E. Pimentel, and K. T. Nguyen, editors, 42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025, March 4-7, 2025, Jena, Germany, volume 327 of LIPIcs...

    work page 2025

  30. [30]

    Foucaud, S

    F. Foucaud, S. Kao, R. Klasing, M. Miller, and J. Ryan. Monitoring the edges of a graph using distances. Discrete Applied Mathematics, 319:424–438, 2022

    work page 2022

  31. [31]

    Foucaud, R

    F. Foucaud, R. Klasing, M. Miller, and J. Ryan. Monitoring the edges of a graph using distances. In M. Changat and S. Das, editors, Proceedings of CALDAM 2020, volume 12016 of Lecture Notes in Computer Science, pages 28–40, 2020

    work page 2020

  32. [32]

    Foucaud, P

    F. Foucaud, P. Marcille, Z. M. Myint, R. B. Sandeep, S. Sen, and S. Taruni. Monitoring edge-geodetic sets in graphs: Extremal graphs, bounds, complexity. In S. Kalyanasundaram and A. Maheshwari, editors, Algorithms and Discrete Applied Mathematics - 10th International Conference, CALDAM 2024, Bhilai, India, February 15-17, 2024, Proceedings, volume 14508 ...

    work page 2024

  33. [33]

    Foucaud, K

    F. Foucaud, K. Narayanan, and L. R. Sulochana. Monitoring edge-geodetic sets in graphs. In A. Bagchi and R. Muthu, editors, Proceedings of CALDAM 2023, volume 13947 of Lecture Notes in Computer Science, pages 245–256, 2023

    work page 2023

  34. [34]

    Gallai and A

    T. Gallai and A. N. Milgram. Verallgemeinerung eines graphentheoretischen Satzes von R´ edei.Acta Scientiarum Mathematicarum, 21(3-4):181–186, 1960

    work page 1960

  35. [35]

    Harary, E

    F. Harary, E. Loukakis, and C. Tsouros. The geodetic number of a graph. Mathematical and Computer Modelling, 17(11):89–95, 1993

    work page 1993

  36. [36]

    Harary and R

    F. Harary and R. Melter. On the metric dimension of a graph. Ars Combinatoria, 2:191–195, 1976

    work page 1976

  37. [37]

    Haslegrave

    J. Haslegrave. Monitoring edge-geodetic sets: hardness and graph products. Discrete Applied Math- ematics, 340:79–84, 2023

    work page 2023

  38. [38]

    Z. Ji, R. Klasing, W. Li, Y. Mao, and X. Zhang. Erd¨ os-gallai-type problems for distance-edge- monitoring numbers. Discret. Appl. Math., 342:275–285, 2024

    work page 2024

  39. [39]

    H. Jung. On a class of posets and the corresponding comparability graphs. Journal of Combinatorial Theory, Series B, 24(2):125–133, 1978. 15

    work page 1978

  40. [40]

    Katsikarelis, M

    I. Katsikarelis, M. Lampis, and V. T. Paschos. Structural parameters, tight bounds, and approxi- mation for (k, r)-center. Discrete Applied Mathematics, 264:90–117, 2019

    work page 2019

  41. [41]

    Katsikarelis, M

    I. Katsikarelis, M. Lampis, and V. T. Paschos. Structurally parameterized d-scattered set. Discrete Applied Mathematics, 308:168–186, 2022

    work page 2022

  42. [42]

    Kelenc, D

    A. Kelenc, D. Kuziak, A. Taranenko, and I. G. Yero. Mixed metric dimension of graphs. Applied Mathematics and Computation, 314:429–438, 2017

    work page 2017

  43. [43]

    Kelenc, N

    A. Kelenc, N. Tratnik, and I. G. Yero. Uniquely identifying the edges of a graph: The edge metric dimension. Discrete Applied Mathematics, 251:204–220, 2018

    work page 2018

  44. [44]

    Kellerhals and T

    L. Kellerhals and T. Koana. Parameterized complexity of geodetic set. Journal of Graph Algorithms and Applications, 26(4):401–419, 2022

    work page 2022

  45. [45]

    Khuller, B

    S. Khuller, B. Raghavachari, and A. Rosenfeld. Landmarks in graphs. Discrete Applied Mathematics, 70(3):217–229, 1996

    work page 1996

  46. [46]

    M. Knor, S. Majstorovi´ c, A. T. Masa Toshi, R. ˇSkrekovski, and I. G. Yero. Graphs with the edge metric dimension smaller than the metric dimension. Applied Mathematics and Computation, 401:126076, 2021

    work page 2021

  47. [47]

    Komusiewicz and R

    C. Komusiewicz and R. Niedermeier. New races in parameterized algorithmics. In B. Rovan, V. Sas- sone, and P. Widmayer, editors, Proceedings of MFCS 2012, volume 7464 of Lecture Notes in Com- puter Science, pages 19–30, 2012

    work page 2012

  48. [48]

    Kuziak and I

    D. Kuziak and I. G. Yero. Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results. arXiv preprint arXiv:2107.04877, 2021

    Pith/arXiv arXiv 2021

  49. [49]

    H. Le, V. B. Le, and H. M¨ uller. Splitting a graph into disjoint induced paths or cycles. Discrete Applied Mathematics, 131(1):199–212, 2003

    work page 2003

  50. [50]

    Li and M

    S. Li and M. Pilipczuk. Hardness of metric dimension in graphs of constant treewidth. Algorithmica, 84(11):3110–3155, 2022

    work page 2022

  51. [51]

    C. V. G. C. Lima, V. F. d. Santos, J. H. G. Sousa, and S. A. Urrutia. On the computational complexity of the strong geodetic recognition problem. RAIRO - Operations Research, 58(5):3755– 3770, 2024

    work page 2024

  52. [52]

    Lov´ asz

    L. Lov´ asz. On covering of graphs. In P. Erd˝ os and G. Katona, editors, Theory of Graphs, pages 231–236. Akad´ emiai Kiad´ o, Budapest, 1968

    work page 1968

  53. [53]

    C. Lu, Q. Ye, and C. Zhu. Algorithmic aspect on the minimum (weighted) doubly resolving set problem of graphs. Journal of Combinatorial Optimization, 44:2029 – 2039, 2022

    work page 2029

  54. [54]

    Manuel, S

    P. Manuel, S. Klavˇ zar, A. Xavier, A. Arokiaraj, and E. Thomas. Strong edge geodetic problem in networks. Open Mathematics, 15(1):1225–1235, 2017

    work page 2017

  55. [55]

    P. D. Manuel. Revisiting path-type covering and partitioning problems. arXiv preprint arXiv:1807.10613, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  56. [56]

    P. D. Manuel, B. Breˇ sar, and S. Klavˇ zar. The geodesic-transversal problem. Applied Mathematics and Computation, 413:126621, 2022

    work page 2022

  57. [57]

    T. McCabe. A complexity measure. IEEE Transactions on Software Engineering, SE-2(4):308–320, 1976

    work page 1976

  58. [58]

    Ntafos and S

    S. Ntafos and S. Hakimi. On path cover problems in digraphs and applications to program testing. IEEE Transactions on Software Engineering, SE-5(5):520–529, 1979

    work page 1979

  59. [59]

    O. R. Oellermann and J. Peters-Fransen. The strong metric dimension of graphs and digraphs. Discrete Applied Mathematics, 155(3):356–364, 2007. 16

    work page 2007

  60. [60]

    I. M. Pelayo. Geodesic Convexity in Graphs. Springer, 2013

    work page 2013

  61. [61]

    Peterin and G

    I. Peterin and G. Semaniˇ sin. On the maximal shortest paths cover number. Mathematics, 9(14), 2021

    work page 2021

  62. [62]

    Sedlar and R

    J. Sedlar and R. ˇSkrekovski. Bounds on metric dimensions of graphs with edge disjoint cycles. Applied Mathematics and Computation, 396:125908, 2021

    work page 2021

  63. [63]

    Sedlar and R

    J. Sedlar and R. ˇSkrekovski. Extremal mixed metric dimension with respect to the cyclomatic number. Applied Mathematics and Computation, 404:126238, 2021

    work page 2021

  64. [64]

    Sedlar and R

    J. Sedlar and R. ˇSkrekovski. Mixed metric dimension of graphs with edge disjoint cycles. Discrete Applied Mathematics, 300:1–8, 2021

    work page 2021

  65. [65]

    Sedlar and R

    J. Sedlar and R. ˇSkrekovski. Metric dimensions vs. cyclomatic number of graphs with minimum degree at least two. Applied Mathematics and Computation, 427:127147, 2022

    work page 2022

  66. [66]

    Sedlar and R

    J. Sedlar and R. ˇSkrekovski. Vertex and edge metric dimensions of cacti. Discrete Applied Mathe- matics, 320:126–139, 2022

    work page 2022

  67. [67]

    P. J. Slater. Leaves of trees. In Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), pages 549–559. Congressus Numerantium, No. XIV, Winnipeg, Man., 1975. Utilitas Math

    work page 1975

  68. [68]

    P. Tale. Geodetic set on graphs of constant pathwidth and feedback vertex set number. arXiv eprint,

    work page

  69. [69]

    Thiessen and T

    M. Thiessen and T. Gaertner. Active learning of convex halfspaces on graphs. In Proceedings of the 35th Conference on Neural Information Processing Systems, NeurIPS 2021, volume 34, pages 23413–23425. Curran Associates, Inc., 2021

    work page 2021

  70. [70]

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

    work page 2023

  71. [71]

    Uhlmann and M

    J. Uhlmann and M. Weller. Two-layer planarization parameterized by feedback edge set. Theoretical Computer Science, 494:99–111, 2013

    work page 2013

  72. [72]

    C. Wang, Y. Song, G. Fan, H. Jin, L. Su, F. Zhang, and X. Wang. Optimizing cross-line dispatching for minimum electric bus fleet. IEEE Transactions on Mobile Computing, 22(4):2307–2322, 2023

    work page 2023

  73. [73]

    H. Whitney. Non-separable and planar graphs. Proceedings of the National Academy of Sciences, 17(2):125–127, 1931

    work page 1931

  74. [74]

    C. Yang, R. Klasing, Y. Mao, and X. Deng. On the distance-edge-monitoring numbers of graphs. Discrete Applied Mathematics, 342:153–167, 2024

    work page 2024

  75. [75]

    C. Yang, G. Yang, S.-Y. Hsieh, Y. Mao, and R. Klasing. Monitoring the edges of a graph using distances with given girth. Journal of Computer and System Sciences, 143:103528, 2024

    work page 2024

  76. [76]

    Zubrilina

    N. Zubrilina. On the edge dimension of a graph. Discrete Mathematics, 341(7):2083–2088, 2018. 17

    work page 2083

  77. [2025]

    https://arxiv.org/abs/2504.17862

    Pith/arXiv arXiv

This paper was first reviewed by deepseek-v4-flash on August 5, 2026.