pith. sign in

arxiv: 2604.14405 · v1 · submitted 2026-04-15 · 🧮 math.CO

Infinite graphs with finite metric dimension

Csaba Bir\'o , Caroline E. Boone , Beth Novick , Hazel Torek This is my paper

Pith reviewed 2026-05-10 12:30 UTC · model grok-4.3

classification 🧮 math.CO
keywords metric dimensioninfinite graphsgraph endsresolving setsstrong dimensionweak dimensiondegree three verticescycles
0
0 comments X

The pith

Infinite graphs with more than one end have infinite strong metric dimension, with finite weak and strong dimensions characterized for finitely-cyclic graphs by the number of ends and degree-three vertices.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines precisely when infinite graphs admit finite metric dimension in its strong and weak forms. It proves that any graph with two or more ends must have infinite strong metric dimension. For graphs containing only finitely many cycles, the weak metric dimension is finite exactly when the graph has finitely many vertices of degree three, while the strong metric dimension is finite exactly when the graph has one end and finitely many vertices of degree three. These characterizations show how local vertex degrees and global end structure together control the size of the smallest resolving set in the infinite setting.

Core claim

The authors prove that every connected infinite graph with at least two ends has infinite strong metric dimension. When the graph has only finitely many cycles, the weak metric dimension is finite if and only if there are finitely many vertices of degree three, and the strong metric dimension is finite if and only if the graph has exactly one end and finitely many vertices of degree three.

What carries the argument

Strong and weak metric dimensions, given by the smallest size of a resolving set whose distance vectors distinguish all vertices, with ends of the graph serving as the global obstruction.

Load-bearing premise

The graphs are connected and undirected, and the if-and-only-if statements apply only when the graph has finitely many cycles.

What would settle it

A connected infinite graph with two or more ends that nevertheless admits a finite strong resolving set would falsify the first claim; a graph with finitely many cycles, infinitely many degree-three vertices, and finite weak metric dimension would falsify the second.

Figures

Figures reproduced from arXiv: 2604.14405 by Beth Novick, Caroline E. Boone, Csaba Bir\'o, Hazel Torek.

Figure 1
Figure 1. Figure 1: Infinite Ladder v1 v2 · · · [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Infinite Broken Ladder 3. Graphs with multiple ends In the quest to characterize infinite graphs with finite dimension, it is useful to find large classes of graphs that are definitely not candidates. In this section, we show that graphs with more than one end have infinite strong dimension. In fact, we will prove a slightly stronger statement, deducing this theorem as a corollary. We will use the usual no… view at source ↗
Figure 3
Figure 3. Figure 3: k-spider Suppose there is w ∈ W that resolves u, v; without loss of generality, a u–w shortest path contains v. First we will prove that d(u, v) ≥ d(u) + d(v). To see this, let P be a shortest u–v path. Notice that P contains a vertex w0 ∈ W. Then d(u, v) = d(u, w0) + d(w0, v) ≥ d(u) + d(v). Now let w ′ ∈ W be such that d(u, w′ ) = d(u) (note that w ′ = w0 is possible). Then, d(u, w) ≤ d(u, w′ ) + d(w ′ , … view at source ↗
Figure 4
Figure 4. Figure 4: P and Q Note that u − ∈ {a, v−} or u + ∈ {b, v+} are possible. Let C be u −P u+Qu−. Note that C contains no repeated vertex, and hence is a cycle, which contains v −, v, v + in this order on the u −P u+ portion. □ 4.1. Characterization of locally finite finicyclic graphs. A finicyclic graph can be made into a forest by the removal of finitely many vertices, since only one vertex must be removed from each c… view at source ↗
Figure 5
Figure 5. Figure 5: The infinite binary tree has an uncountable number of rays. Each ray can be described by the binary representation of any number in [0, 1]. (a) d(vi , w) > d(w, R) for all w ∈ W; (b) vi has empty intersection with every cycle in G. Now let ℓ be the smallest integer with ℓ ≥ k and deg(vℓ) ≥ 3. Let v ′ be a vertex adjacent to vℓ other than vℓ−1 or vℓ+1. Property (b) guarantees that v ′ is not on R. Let m be … view at source ↗
Figure 6
Figure 6. Figure 6: The vertices u, v are a bad pair in GW when G is the infinite broken ladder and W = {w1, w2}. u, v ∈ V (G), and assume that u, v ̸∈ W′ . Then u, v ∈ R1. Without loss of generality, d(u, r1) < d(v, r1) (they can not be equal), so then u is on a shortest v–r1 path in G. □ We summarize the findings of this section in the following corollary. Corollary 4.11. Let G be an infinite finicyclic graph. • The weak di… view at source ↗
read the original abstract

We study the metric dimension (strong and weak) of infinite graphs. In particular, our main interest is characterizing infinite graphs with finite dimension. Our main results: (1) graphs with more than one end have infinite strong dimension; (2) for graphs with a finite number of cycles, the weak dimension is finite if and only if the graph has finitely many vertices of degree three, and the strong dimension is finite if and only if the graph has one end and finitely many vertices of degree three.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript studies the metric dimension (strong and weak variants) of infinite graphs. Its main results are: (1) any graph with more than one end has infinite strong dimension; (2) for graphs with finitely many cycles, the weak dimension is finite if and only if there are finitely many degree-3 vertices, while the strong dimension is finite if and only if the graph has exactly one end and finitely many degree-3 vertices.

Significance. If the characterizations are correct, the work provides precise structural criteria linking the number of ends and local vertex degrees to the existence of finite resolving sets in infinite graphs. This extends the theory of metric dimension beyond finite graphs using standard tools such as graph ends, and the clean if-and-only-if statements (under the finite-cycle hypothesis) represent a substantive advance that could support further results on resolvability and infinite combinatorial invariants.

minor comments (2)
  1. The abstract and introduction should explicitly recall or cite the precise definitions of strong metric dimension and weak metric dimension (including how resolving sets are defined for infinite graphs) to ensure the characterizations are self-contained.
  2. Add a short comparison with known results on metric dimension for finite graphs or for graphs with infinite cycles to better situate the novelty of the finite-cycle case.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and for recommending minor revision. The referee correctly summarizes our main results on the strong and weak metric dimensions of infinite graphs, particularly the characterizations under the finite-cycle hypothesis. We confirm that these if-and-only-if statements hold as stated. Since the report contains no specific major comments or requested changes, we see no need for revisions at this time.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper derives characterizations of finite strong and weak metric dimension for infinite graphs directly from the standard definitions of resolving sets, metric dimension, and graph ends, together with the assumption of finitely many cycles. No equations reduce a claimed prediction to a fitted parameter by construction, no uniqueness theorem is imported from the authors' prior work, and no ansatz or renaming of known results is presented as a derivation. The central iff statements rest on properties of resolving sets in graphs with finite cycle space, which are independent of the target claims and do not collapse to self-definition or self-citation chains.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The results rest on standard definitions from graph theory (connected undirected graphs, distance functions, graph ends, strong vs. weak resolving sets) with no free parameters, no invented entities, and no ad-hoc axioms beyond the usual background.

axioms (2)
  • domain assumption Graphs are undirected, connected, and locally finite
    Implicit in all metric-dimension studies of infinite graphs and required for the notions of ends and degree to be well-defined.
  • standard math Strong and weak metric dimension are defined via distance vectors to a resolving set
    Core definition used throughout the field; invoked to state the finiteness conditions.

pith-pipeline@v0.9.0 · 5372 in / 1312 out tokens · 25721 ms · 2026-05-10T12:30:32.024763+00:00 · methodology

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

13 extracted references · 13 canonical work pages

  1. [1]

    Aharoni and E

    R. Aharoni and E. Berger. Menger’s theorem for infinite graphs.Invent. Math., 176(1):1–62, 2009

    work page 2009

  2. [2]

    Belmonte, F

    R. Belmonte, F. V. Fomin, P. A. Golovach, and M. S. Ramanujan. Metric dimension of bounded width graphs. InMathematical foundations of computer science 2015. Part II, volume 9235 ofLecture Notes in Comput. Sci., pages 115–126. Springer, Heidelberg, 2015

    work page 2015

  3. [3]

    Benakli, N

    N. Benakli, N. H. Bong, S. Dueck, B. Novick, and O. R. Oellermann. The threshold dimension and threshold strong dimension of a graph: a survey. InResearch trends in graph theory and applications, volume 25 ofAssoc. Women Math. Ser., pages 73–98. Springer, Cham, [2021] ©2021

    work page 2021

  4. [4]

    C´ aceres, C

    J. C´ aceres, C. Hernando, M. Mora, I. M. Pelayo, and M. L. Puertas. On the metric dimension of infinite graphs.Discrete Applied Math., 160(18):2618–2626, 2012

    work page 2012

  5. [5]

    C´ aceres, C

    J. C´ aceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara, and D. R. Wood. On the metric dimension of Cartesian products of graphs.SIAM J. Discrete Math., 21(2):423– 441, 2007

    work page 2007

  6. [6]

    Chartrand, L

    G. Chartrand, L. Eroh, M. Johnson, and O. Oellermann. Resolvability in graphs and the metric dimension of a graph.Discrete App. Math., 105:99–113, 2000

    work page 2000

  7. [7]

    Diestel.Graph Theory

    R. Diestel.Graph Theory. Springer, 5. edition, 2017

    work page 2017

  8. [8]

    Harary and R

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

    work page 1976

  9. [9]

    Khuller, B

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

    work page 1996

  10. [10]

    Kratica, V

    J. Kratica, V. Kovaˇ cevi´ c-Vujˇ ci´ c, M.ˇCangalovi´ c, and N. Mladenovi´ c. Strong metric dimension: a survey.Yugosl. J. Oper. Res., 24(2):187–198, 2014

    work page 2014

  11. [11]

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

    work page 2007

  12. [12]

    Seb˝ o and E

    A. Seb˝ o and E. Tannier. On metric generators of graphs.Mathematics of Operations Research, 29(2):383–393, 2004

    work page 2004

  13. [13]

    P. J. Slater. Leaves of trees.Cong. Numer., 14:549–559, 1975. Department of Mathematics, University of Louisville, Louisville, KY 40292 Email address:csaba.biro@louisville.edu Department of Mathematics, University of Louisville, Louisville, KY 40292 Email address:caroline.boone@louisville.edu School of Mathematical and Statistical Sciences, Clemson Univer...

    work page 1975