# Metric dimension on sparse graphs and its applications to zero forcing
sets111An extended abstract of this work has been published in EuroComb 2021
[1]. 222The first three authors of this work are supported by ANR project GrR
(ANR-18-CE40-0032). The Ignacio M. Pelayo work is supported by project
PGC2018-095471-B-100.

Nicolas Bousquet  Université de Lyon, Université Lyon 1, LIRIS UMR CNRS 5205,
F-69621, Lyon, France  Quentin Deschamps  Université de Lyon, Université Lyon
1, LIRIS UMR CNRS 5205, F-69621, Lyon, France  Aline Parreau  Université de
Lyon, Université Lyon 1, LIRIS UMR CNRS 5205, F-69621, Lyon, France  Ignacio
M. Pelayo  Universitat Politècnica de Catalunya, Barcelona, Spain

###### Abstract

The metric dimension $\dim(G)$ of a graph $G$ is the minimum cardinality of a
subset $S$ of vertices of $G$ such that each vertex of $G$ is uniquely
determined by its distances to $S$. It is well-known that the metric dimension
of a graph can be drastically increased by the modification of a single edge.
Our main result consists in proving that the increase of the metric dimension
of an edge addition can be amortized in the sense that if the graph consists
of a spanning tree $T$ plus $c$ edges, then the metric dimension of $G$ is at
most the metric dimension of $T$ plus $6c$.

We then use this result to prove a weakening of a conjecture of Eroh et al.
The zero forcing number $Z(G)$ of $G$ is the minimum cardinality of a subset
$S$ of black vertices (whereas the other vertices are colored white) of $G$
such that all the vertices will turned black after applying finitely many
times the following rule: _a white vertex is turned black if it is the only
white neighbor of a black vertex._

Eroh et al. conjectured that, for any graph $G$, $\dim(G)\leq Z(G)+c(G)$,
where $c(G)$ is the number of edges that have to be removed from $G$ to get a
forest. They proved the conjecture is true for trees and unicyclic graphs. We
prove a weaker version of the conjecture: $\dim(G)\leq Z(G)+6c(G)$ holds for
any graph. We also prove that the conjecture is true for graphs with edge
disjoint cycles, widely generalizing the unicyclic result of Eroh et al.

##  1 Introduction

A _resolving set_ of a graph $G$ is a subset of vertices of $G$ such that any
vertex in the graph is identified by its distances to the vertices of the
resolving set. In the example of Figure 1 the set $\\{u,v\\}$ is a resolving
set of the graph because all the vertices have a different _distance vector_
to $\\{u,v\\}$ so the knowledge of the distances to $u$ and $v$ uniquely
identifies a vertex. This notion has been introduced in 1975 by Slater [2] for
trees and by Harary and Melter [3] for graphs. Determining the minimum size of
a resolving set, called _metric dimension_ and denoted by $\dim(G)$, is an NP-
hard problem [4] even restricted to planar graphs [5]. Applications of metric
dimension go from piloting a sonar [3] to the navigation of a robot in an
Euclidean space [6].

Figure 1: The black vertices form a resolving set. For each vertex $x$ the
vector next to $x$, $(d(u,x),d(v,x))$ is unique.

One of the main issues to compute the metric dimension of a graph comes from
the fact that it is unstable when the graph is modified. When a vertex is
added, the metric dimension can be drastically modified. Indeed, while a path
admits a constant size resolving set, a path plus a universal vertex only
admits resolving sets of linear size (in the number of vertices). However, in
this example even if only one vertex was added, a linear number of edges were
also added which had permitted to put all the vertices at distance $2$. One
can then wonder if the situation is better when only one edge is modified in
the graph. Unfortunately again, the metric dimension of a graph can be
drastically modified by the modification of a single edge. In Figure 2 (first
proposed in [7]), the metric dimension of the left graph is $2k$ where $k$ is
the number of layers in the graph while the right graph has metric dimension
$k+1$. So the addition of one edge can modify the metric dimension by
$\Omega(n)$.

Figure 2: On the left graph, all the pairs $(c_{i},d_{i})$ are twins (both
vertices have the same neighborhood) so for all $i\leq k$ any resolving set
should contain $c_{i}$ or $d_{i}$. Then, for $i\leq k$, the pair
$(x_{i},y_{i})$ can only be resolved by a vertex of $E_{i}$ so any resolving
set should contain a vertex of $E_{i}$ for all $i\leq k$. So any resolving set
contains at least $2k$ vertices. The set of black vertices is a resolving set
so the dimension is $2k$. On the right graph the pairs $(c_{i},d_{i})$ are
twins so for all $i\leq k$ any resolving set should contain $c_{i}$ or
$d_{i}$. One can easily check that a set containing only vertices on
$\\{c_{i};d_{i},1\leq i\leq k\\}$ is not resolving so the dimension is higher
than $k$. Black vertices form a resolving set so the metric dimension is
$k+1$.

#### Metric dimension and cycle rank.

Eroh et al. [8] proved that, if $G$ is a unicyclic graph, then the metric
dimension of $G$ is at most the metric dimension of any spanning tree of $G$
plus one. Moreover, all the existing examples where the metric dimension is
drastically modified with an edge modification already contain many cycles.
One can then wonder if the metric dimension of a graph which does not contain
many cycles is close to the metric dimension of any of its spanning trees. The
goal of this paper is to answer this question positively.

One can easily remark that in the star $K_{1,n}$, any resolving set contains
at least $n-1$ vertices. Indeed otherwise, two degree $1$ vertices are not in
the resolving set and then these two vertices cannot be distinguished. This
argument can be generalized to any graph as follows: if $r$ pending paths are
attached to a vertex $v$, any resolving set contains a vertex in at least
$r-1$ of them. Let $L(G)$ be the sum over all the vertices $v$ on which there
are attached pending paths, of the number of paths attached to $v$ minus one
per vertex $v$. Chartrand et al. [9] remarked that, for every connected graph
$G$, $\dim(G)\geq L(G)$ with equality for trees. However, this bound has no
reason to be closed to the optimal value (a graph with no degree $1$ vertex
can have an arbitrarily large metric dimension). A wheel (induced cycle plus a
universal vertex), for instance, has no degree $1$ vertex and its metric
dimension is linear in $n$ (see Figure 5).

The _cycle rank_ of a connected graph, denoted by $c(G)$, is the number of
edges that has to be removed from $G$ to obtain a spanning tree. We prove that
the following holds:

######  Theorem 1.

For any graph $G$, $L(G)\leq\dim(G)\leq L(G)+6c(G)$.

Since the value of $L(G)$ cannot decrease by removing edges in $G$ that are
not bridges, it implies the following:

######  Corollary 2.

Let $G$ be a graph and $T$ be any spanning tree of $G$. Then,

$\dim(G)\leq\dim(T)+6c(G)$

Informally, Corollary 2 ensures that, even if the metric dimension can be
widely modified when we add a single edge, the “amortized cost” of an edge
addition is at most $6$ with respect to any spanning tree of $G$. As far as we
know it is the first bound of the metric dimension in terms of the natural
lower bound $L(G)$ or of the metric dimension of a spanning tree of $G$.

Before explaining briefly the outline of the proof, let us discuss a bit the
tightness of these results. Let $k\in\mathbb{N}$. Consider the graph $G_{k}$
which is a collection of $k$ $C_{4}$ glued on the central vertex of a path of
length $3$ like in Figure 4. The metric dimension of $G_{k}$ is equal to
$2k+1$ (we need to select exactly two vertices per $C_{4}$ distinct from the
center and one extremity of the path), $L(G_{k})=1$, and $c=k$. Since
$L(G_{k})=1$ for every $k$, there exist graphs $G$ such that
$\dim(G)=L(G)+2c(G)$. We ask the following question:

######  Question 3.

Is it true that for any graph $G$, $\dim(G)\leq L(G)+2c(G)$ ?

Note that Sedlar and Skrekovski independently ask the same question in [10].
The same authors also prove in [11] that Question 3 is true for cacti (and
tight since $G_{k}$ is a cactus).

Let us now discuss the tightness of Corollary 2. If, in the graph $G_{k}$, we
remove one edge of each $C_{4}$ incident to the central vertex, the resulting
spanning tree has metric dimension of order $k+1$ as long as $k\geq 2$. So
there exist graphs $G$ for which there exists a spanning tree $T$ satisfying
$\dim(G)=\dim(T)+c$. We actually ask the following question:

######  Question 4.

Is it true that for any graph $G$ and for every spanning tree $T$ of $G$, we
have $\dim(G)\leq\dim(T)+c$?

One can then wonder what happens if we select the best possible spanning tree
to start with, i.e., the spanning tree that maximizes the metric dimension. In
$G_{k}$, one can note that if we break the edges of the $C_{4}$s that are not
incident to the center and denote by $T_{k}$ the resulting tree, then
$\dim(G_{k})=\dim(T_{k})+1$. Surprisingly, we did not find any graph $G$ where
the metric dimension is a function of $c$ larger than any spanning tree of
$G$. We left the existence of such a graph as an open problem.

Let us now briefly discuss the main ingredients of the proof of Theorem 1.
First, it consists in finding a small feedback vertex set $X$ of the graph
such that every connected component is attached to at most two vertices of
$X$. We then prove that, if we add to a resolving set of every connected
component of $G\setminus X$ few vertices (in terms of $c$) we can “detect”
shortcuts passing through the rest of the graph and then obtain a resolving
set of the whole graph $G$. The proof of Theorem 1 is given in Section 3.

The second part of the paper consists in applying this result in order to
prove a weak version of a conjecture linking metric dimension and zero forcing
sets in graphs.

#### Zero forcing sets.

A zero forcing set is a subset of vertices colored in black which colors the
whole vertex set in black when we apply the following rule: _A vertex is
colored black if it is the unique non-black neighbor of a black vertex_. See
Figure 3 where the initial set contains three black vertices. The _zero
forcing number_ of a graph is the minimal size of a zero forcing set, denoted
by $Z(G)$. The zero forcing number has been introduced in 2008 to bound the
rank of some families of adjacency matrices [12]. Deciding if the zero forcing
number of a graph is at most $k$ is NP-complete [13].

Figure 3: Iterations of the change color rule. On the graph on the left, the
three black vertices form a zero forcing set.

In general, the gap between metric dimension and zero forcing number can be
arbitrarily large. But for some restricted sparse graph classes like paths or
cycles, both the optimal parameters and optimal sets are the same. Eroh, Kang
and Yi then started a systematic comparison between them [8]. They proved that
$\dim(G)\leq Z(G)$ when $G$ is a tree and that $\dim(G)\leq Z(G)+1$ when $G$
has one cycle (in other words $G$ is a tree plus an edge). On the other hand,
$\dim(G)$ can be arbitrarily larger than the zero forcing number when the
number of cycles increases. They conjectured the following:

######  Conjecture 5 (Cycle-rank conjecture [8]).

For a connected graph, $\dim(G)\leq Z(G)+c(G)$.

Conjecture 5 is tight for an infinite family of graphs: The graph $G_{k}$
contains a path of $3$ vertices and $k$ cycles of size $4$ with the central
vertex of the path in common. Figure 4 shows the graph $G_{3}$ with
$c(G_{3})=3$.

Figure 4: Tightness of Conjecture 5.

Eroh et al. proved in [8] that $\dim(G)\leq Z(G)+2c(G)$ if $G$ contains no
even induced cycles. Our main contribution to this question is to prove a
weaker version of Conjecture 5 in Section 4.1, whose proof is mainly based on
an application of Theorem 1.

######  Theorem 6.

For every graph $G$, we have

$\dim(G)\leq Z(G)+6c(G).$

As far as we know, it is the first upper bound of $\dim(G)$ of the form
$Z(G)+f(c(G))$.

Note that the dependency on $c(G)$ cannot be removed, i.e., $\dim(G)$ cannot
be upper bounded by a function of $Z(G)$ only. For the wheel of $n$ vertices
(a cycle plus a universal vertex, see Figure 5), the zero forcing number is
$3$ for any $n\geq 4$ but the metric dimension is a linear function in $n$.

Figure 5: The zero forcing number of a wheel is $3$ (while $n\geq 4$) but its
metric dimension is linear in $n$.

We also prove Conjecture 5 in several particular cases. We first focus on
unicyclic graphs. We give an alternative proof of Conjecture 5 for unicyclic
graphs with a much shorter and simpler proof than the one of [8]. We then
extend our results to prove Conjecture 5 for cactus graphs333This result is
proved independently in [10] with a different method. (graphs with edge-
disjoint cycles). It generalizes the result on unicyclic graphs and is based
on a very simple induction whose base case is the case of unicyclic graphs.
Since cactus graphs contain the class of graphs with no even cycles, it
improves the result of [8] on even-cycle-free graphs.

We finally show that $\dim(G)\leq Z(G)$ when the unique cycle of $G$ has odd
length. This result is tight and cannot be extended to unicyclic graphs with
an even cycle as shown in Figure 6. All the results related to zero forcing
sets are proved in Section 4.

Figure 6: Black vertices form respectively a minimal resolving set and a
minimal zero forcing set.

##  2 Preliminaries

###  2.1 Definitions and notations

Unless otherwise stated, all the graphs considered in this paper are
undirected, simple, finite and connected. For standard terminology and
notations on graphs, we refer the reader to [14].

Let $G=(V,E)$ be a graph. The _distance_ between two vertices $u,v\in V$,
denoted by $d_{G}(u,v)$ (or simply $d(u,v)$ when $G$ is clear from context),
is the length of a shortest path from $u$ to $v$ in $G$. When no such path
exists, we state $d_{G}(u,v)=+\infty$. For $v\in V$, let $N(v)$ be the (open)
neighborhood of $v$ defined as $N(v)=\\{u\in V,\;uv\in E\\}$. We say that two
vertices $v$ and $w$ are _twins_ if
$N(v)\setminus\\{w\\}=N(w)\setminus\\{v\\}$. For $X\subseteq V$, let $G[X]$ be
the subgraph of $G$ induced by $X$. In other words, $G[X]$ is the graph with
vertex set $X$ where $xy$ is an edge if and only if it is an edge of $G$. We
denote by $G\setminus X$ the subgraph of $G$ induced by $V\setminus X$. The
_border of $X$_, denoted by $\partial X$, is $\\{u\in G\setminus X|\;\exists
v\in X,uv\in E\\}$.

A vertex $w\in V$ _resolves_ a pair of vertices $(u,v)$ if $d(w,u)\neq
d(w,v)$. Let $S\subseteq V$. The set $S$ _resolves_ the pair $(u,v)$ if at
least one vertex in $S$ resolves the pair $(u,v)$ and $S$ resolves a set
$W\subseteq V$ if $S$ resolves all the pairs of $W$. A set $S$ is a _resolving
set_ of $G$ if $S$ resolves $V$. _The metric dimension_ $\dim(G)$ of $G$ is
the minimum cardinality of a resolving set in $G$. A resolving set of minimum
size is called a _metric basis_.

Let $Z\subseteq V$ be a set of vertices. The vertices in $Z$ are colored in
black whereas the other vertices are white. The _color change rule_ converts a
white vertex $u$ into a black vertex if $u$ is the only white neighbor of a
black vertex. The set $Z$ is a _zero forcing set_ of $G$ if all the vertices
of $G$ can be turned black after finitely many applications of the color
change rule. For $u$ and $v$ two vertices in $V$ and a sequence of
applications of the color change rule, we say that $u$ _forces_ $v$ if at some
step $u$ is turned black with the color change rule because of $v$. We say
that the edge $uv$ is used to force $u$. _The zero forcing number_ $Z(G)$ of
$G$ is the minimal cardinality of a zero forcing set in $G$.

The _cycle rank_ of $G$, denoted by $c(G)$ (or $c$ if the context is clear
enough), is the minimum number of edges that should be deleted from $G$ to get
a forest. Note that we have $c(G)=|E|-|V|+cc(G)$ where $cc(G)$ is the number
of connected components of $G$. A graph $G$ is _unicyclic_ if $G$ is connected
with $c(G)=1$. A feedback vertex set of $G$ is a subset of vertices such that
$G\setminus X$ is a forest. We denote by $\tau(G)$ (or $\tau$ if the context
is clear enough) the minimum size of a feedback vertex set of $G$. Note that
if $X$ has minimum size, then $\tau(G)\leq c(G)$.

###  2.2 Resolving sets and zero forcing sets on trees

Chartrand et al. [9] introduced the following terminology to study resolving
sets in trees. We extend this terminology to general graphs (see Figure 7 for
an illustration).
A vertex of degree $1$ is called a _terminal vertex_.
A vertex of degree at least 3 is a _major vertex_. A terminal vertex $u$ is
called _a terminal vertex of a major vertex $v$_ if $d(u,v)<d(u,w)$ for every
other major vertex $w$. In other words $u$ and $v$ are linked by a path of
degree $2$ vertices. The _terminal degree_ of a major vertex $v$ is the number
of terminal vertices of $v$, denoted by $ter(v)$. A major vertex is _exterior_
if its terminal degree is positive, and _interior_ otherwise.
A degree-$2$ vertex is an _exterior degree-2 vertex_ if it lies on a path
between a terminal vertex and its major vertex. It is an _interior degree-2
vertex_ otherwise.

Figure 7: Vertices denomination in a graph.

Let $\sigma(G)$ be the sum of the terminal degrees over all the major vertices
in $G$ and $ex(G)$ be the number of exterior major vertices in $G$. Let
$L(G)=\sigma(G)-ex(G)$. If $G$ is a path $P_{n}$ for some $n\geq 1$, let
$L(G)=1$. We can bound $\dim(G)$ and $Z(G)$ with this parameter:

######  Lemma 7.

[8] For any connected graph $G$, $\dim(G)\geq L(G)$ and $Z(G)\geq L(G)$.

######  Lemma 8.

[7] Let $T$ be any tree, then, $dim(T)=L(T)$. Moreover, if $T$ is not a path,
any set containing all but exactly one terminal vertices of every major vertex
is a resolving set of $T$.

There is no similar result on the zero forcing number of a tree. The gap
between the zero forcing number and the metric dimension can be arbitrarily
large on trees.

Lemmas 7 and 8 imply that trees satisfy Conjecture 5. Moreover, the equality
case can be characterized:

######  Lemma 9.

[8] For every tree $T$, $\dim(T)\leq Z(T)$. The equality holds if and only if
$T$ has no interior degree-2 vertices and each major vertex has terminal
degree at least two.

###  2.3 Elementary results on metric dimension

This section is devoted to some elementary results about metric dimension.

######  Lemma 10.

Let $G$ be a graph and $u$, $v$ be two vertices of $G$. Let $s$ and $t$ be two
different vertices on a shortest path between $u$ and $v$. Then, $d(u,s)\neq
d(v,s)$ or $d(u,t)\neq d(v,t)$.

###### Proof.

Let $P$ be a shortest path from $u$ to $v$ containing $s$ and $t$. Up to
symmetry, we can assume that $u,s,t,v$ appear in that order in $P$. Since $P$
is a shortest path, $d(s,v)=d(s,t)+d(t,v)>d(t,v)$ and
$d(t,u)=d(s,u)+d(s,t)>d(s,u)$. Assume that $d(u,s)=d(v,s)$. Then,
$d(u,t)=d(u,s)+d(t,s)$ and $d(v,s)=d(v,t)+d(t,s)$. So,
$d(u,t)=d(v,t)+2d(t,s)\neq d(v,t)$ as $t\neq s$. ∎

######  Lemma 11.

Let $G$ be a unicyclic graph with a cycle $C$ of odd length. Then, every pair
of vertices of $C$ resolves $C$.

###### Proof.

Let $u$ and $v$ be two vertices of $C$. There are two paths between $u$ and
$v$ on $C$, one of odd length and the other of even length. There exists a
unique vertex $w$ of $C$ at the same distance from $u$ and $v$ in $C$ and then
in $G$ since $G$ is unicyclic which is the middle of the path of even length.
The vertex $w$ is the unique vertex of $C$ that does not resolve the pair
$(u,v)$. So any pair of vertices of $C$ resolves $C$. ∎

######  Lemma 12.

Let $G=(V,E)$ be a graph and $C$ be a cycle of $G$. If
$V(C)=\\{v_{0},v_{1},...,v_{k}\\}$ and for any $i\leq j$
$d(v_{i},v_{j})=\min(j-i,k-j+i+1)$ 444This condition ensures that there is no
shortcut between the vertices of $C$., then, for any set $S\subseteq C$ of
size at least $3$, $S$ resolves $C$.

###### Proof.

Let $S=\\{v_{a},v_{b},v_{c}\\}$ be any set of three vertices of $C$ and
$v_{x}\neq v_{y}$ be two vertices of $C$. Assume by contradiction that $S$
does not resolve the pair $(v_{x},v_{y})$.

Note that neither $v_{x}$ nor $v_{y}$ belongs to $\\{v_{a},v_{b},v_{c}\\}$
since otherwise $(v_{x},v_{y})$ would be resolved. Without loss of generality,
we can assume that $v_{x}=v_{0}$ and $a<b<c$.

Assume first that $y<a$. The shortest path on $G$ between $v_{0}$ and $v_{a}$
cannot contain $v_{y}$ otherwise $d(v_{x},v_{a})>d(v_{y},v_{a})$. Thus,
$d(v_{0},v_{a})=k-a+1$ and similarly $d(v_{0},v_{b})=k-b+1$ so in particular
$d(v_{0},b)<d(v_{0},a)$. Consider now the path between $v_{y}$ and $v_{b}$. If
this path passes through $v_{a}$, then $d(v_{y},a)<d(v_{y},b)$ and if this
path passes through $v_{0}$ then $d(v_{y},b)>d(v_{0},b)$. Both cases give a
contradiction with the assumption that $S$ does not resolve the pair
$(v_{0},v_{y})$.

Assume now that $a<y<b$. If the shortest path between $v_{0}$ and $v_{b}$
passes through $v_{y}$ then $d(v_{0},v_{b})>d(v_{y},v_{b})$ gives a
contradiction. Thus, $d(v_{0},v_{b})=k-b+1$ and so $d(v_{0},v_{c})=k-c+1$.
Similarly if the path between $v_{y}$ and $v_{b}$ passes through $v_{0}$ then
$d(v_{y},v_{b})>d(v_{0},v_{b})$. So $d(v_{y},v_{b})=b-y$ and
$d(v_{y},v_{c})=c-y$. We get $b-y=k-b+1$ and $c-y=k-c+1$ which is impossible
since $b\neq c$.

The two last cases, $b<y<c$ and $y>c$, are respectively symmetric to the cases
$a<y<b$ and $y<a$. ∎

The following result has been stated in [8] but the proof contains a flaw. We
provide a corrected version of the proof in Appendix A. It bounds the
variation of the metric dimension when an edge is deleted in some conditions.

######  Lemma 13.

Let $G=(V,E)$ be a graph and $C$ be a cycle of $G$. Let
$V(C)=\\{v_{0},v_{1},...,v_{k}\\}$ be the vertices of $C$. Denote by
$G_{i}=(V_{i},E_{i})$ the connected components of the vertex $u_{i}$ in
$G\setminus E(C)$. If, for every $i\neq j$, $V_{i}\cap V_{j}=\emptyset$, then,
for any $e\in E(C)$, $\dim(G)\leq\dim(G-e)+1$.

The following lemma is a well-known fact about twins and resolving sets.

######  Lemma 14.

Let $u$ and $v$ be two twins of a graph $G$. Any resolving set $S$ of $G$
verifies $S\cap\\{u,v\\}\neq\emptyset$.

Lemma 15 is a crucial observation for studying resolving sets in particular in
trees.

######  Lemma 15.

Let $G=(V,E)$ be a connected graph, $u$ be a vertex of $G$ and $S$ be a
resolving set of $G$. At most one connected component of $G\setminus\\{u\\}$
does not contain any vertex of $S$.

###### Proof.

Assume by contradiction that two connected components $G_{i}$ and $G_{j}$ of
$G\setminus\\{x\\}$ do not contain any vertex of $S$. Let $v\in V$ and $w\in
V(G_{j})$ be two vertices incident to $u$. Then, no vertex in $S$ resolves the
pair $(v,w)$ since, for every $s\in S$, $d(s,v)=d(s,w)=d(s,u)+1$. ∎

##  3 Bounds for the metric dimension

######  Definition 16.

Let $G$ be a graph. Recall that $L(G)=\sigma(G)-ex(G)$. If $G$ is a path
$P_{n}$ for some $n\geq 1$, let $L(G)=1$ (so $L(T)=\dim(T)$ for all trees).

The goal is to prove Theorem 1 we recall here: See 1

This result implies the following one: See 2

###### Proof.

For any graph $G=(V,E)$ that is not a tree and any edge $e\in E$ such that
$G-e$ is connected, $L(G)\leq L(G-e)$. Indeed if a major vertex $v$ has
terminal degree $d\geq 2$ in $G$, then $v$ is still a major vertex in $G-e$ of
terminal degree at least $d$. So $L(G)\leq L(G-e)$ and then, for $T$ a
spanning tree of $G$, $L(G)\leq L(T)$. As $\dim(G)\leq L(G)+6c(G)$ and
$\dim(T)=L(T)$ we get $\dim(G)\leq\dim(T)+6c(G)$. ∎

The rest of the section is devoted to prove Theorem 1.

###  3.1 Construction of the resolving set

If $c(G)=0$ then $G$ is a tree and $\dim(G)=L(G)$ by Lemma 8. If $c(G)=1$ let
us prove a stronger result.

######  Lemma 17.

Let $G=(V,E)$ be a connected unicyclic graph. Then $\dim(G)\leq L(G)+3$.

###### Proof.

Let $uv$ be an edge of the cycle. Let $T=G-e$, then $\dim(T)=L(T)$ by Lemma 8
and $\dim(G)\leq\dim(T)+1$ by Lemma 13. As $L(T)\leq L(G)+2$ we get the
inequality. ∎

We now focus on the case $c(G)\geq 2$. The first part of the proof will
consist in defining a subset $S$ of vertices. We then prove in the second part
of the proof that it is, indeed, a resolving set. In order to build this set
$S$, we first find a small subset of vertices $M$ such that $G\setminus M$ is
a forest and each connected component of $G\setminus M$ has at most two edges
incident to $M$. We then construct the set $S$.

Let us start with a simple lemma.

######  Lemma 18.

Let $G$ be a connected graph with no vertex of degree $1$ that is not an
induced cycle. There exists a feedback vertex set $X$ of size $\tau(G)$
containing only vertices of degrees at least $3$.

###### Proof.

Let $X$ be a minimum feedback vertex set with the minimum number of vertices
of degrees less than $3$. Note that $X$ does not contain vertices of degree
$1$. Assume by contradiction that $X$ contains a vertex $x$ of degree $2$. Let
$P$ be the maximal path of vertices of degree $2$ containing $x$. Since $G$ is
not a cycle (and is not acyclic otherwise $X$ would be empty), $P$ does not
contain the whole graph. Let $y$ be an endpoint of $P$ adjacent to a vertex
$z$ of $V\setminus P$. Let $X^{\prime}=X\setminus\\{x\\}\cup\\{z\\}$. The set
$X^{\prime}$ is still a feedback vertex set, a contradiction with the
minimality of $X$. ∎

Let $X$ be a feedback vertex set of $G$ only containing vertices of degrees at
least $3$ in the graph where all the vertices of degree $1$ have been
iteratively removed555Note that we can assume that the resulting graph is not
a cycle since otherwise the graph is unicyclic and the conclusion follows by
Lemma 17.. Let $G_{1},G_{2},...,G_{k}$ be the connected components of
$G\setminus X$. Note that each $G_{i}$ is a tree. For each $G_{i}$, let
$X_{i}\subseteq X$ be the set of vertices of $X$ connected to at least one
vertex of $G_{i}$. Let $N_{i}\subseteq V(G_{i})$ be the set of vertices in
$G_{i}$ adjacent to (at least) one vertex of $X_{i}$.

Let $T_{i}$ be the minimal subtree of $G_{i}$ containing the vertices of
$N_{i}$. In other words, $T_{i}$ is the subtree of $G_{i}$ restricted to the
union of the paths between $a$ and $b$ for any pair $a,b\in N_{i}$. Let
$T^{\prime}_{i}$ be the tree built from $T_{i}$ by adding to each vertex $u\in
N_{i}$, $|N(u)\cap X|$ pending degree $1$ vertices. Let $M_{i}$ be the set of
vertices in $T^{\prime}_{i}$ of degree at least $3$ and
$M:=X\cup(\bigcup_{i=1}^{k}M_{i})$. Figure 8 illustrates these notations.

Figure 8: Illustration of the notations $X,N_{i},M_{i},T_{i}$ and $G_{i}$.

######  Lemma 19.

For each connected component $H$ of $G\setminus M$ there are at most two edges
in $G$ between $H$ and $G\setminus H$.

###### Proof.

Let $U_{H}$ be the minimal subtree of $H$ containing all the vertices incident
to an edge between $H$ and $G\setminus H$. Then, for each edge between a
vertex $v\in H$ and a vertex in $G\setminus H$, add one new vertex in $U_{H}$
adjacent to $v$. Let us still denote by $U_{H}$ the resulting graph. Note that
$U_{H}$ has as many degree $1$ vertices as edges leaving $H$. So, there are at
most two edges with exactly one endpoint in $H$ if and only if $U_{H}$ has no
vertex of degree three. The graph $U_{H}$ is isomorphic to a subgraph of
$T^{\prime}_{i}$, then, by definition of $T^{\prime}_{i}$, $U_{H}$ does not
contain vertex of degree three.

∎

Lemma 19 indeed implies the following.

######  Corollary 20.

Every connected component of $G\setminus M$ is connected to at most two
vertices of $M$.

A connected component of $G\setminus M$ can be attached to $M$ in three
different ways, called Types, illustrated in Figure 9. A connected component
of $G\setminus M$ has _Type $A$_ (respectively _Type $B$_) if there are
exactly two edges between $H$ and $M$ with distinct endpoints in $H$ and such
that their endpoints in $M$ are distinct (resp. the same). A component $H$ has
_Type $C$_ if all the edges of $G$ between $H$ and $M$ have the same endpoint
in $H$ (but possibly distinct endpoints in $M$).

Let $H$ be a connected component of $G\setminus M$ of Type $A$ or $B$ and let
$x$ and $y$ be the two endpoints in $M$ of the edges between $H$ and $M$. Let
$\rho_{H}$ be one vertex on the path in $H$ between $x$ and $y$ such that
$|d_{H}(x,\rho_{H})-d_{H}(y,\rho_{H})|\leq 1$. In other words, $\rho_{H}$ is
one of the vertices in the middle of the path between $x$ and $y$ in $H$. Let
$P$ be the set of the vertices $\rho_{H}$ for all the connected components $H$
of _Type_ $A$ and $B$.

Figure 9: The three _Types_ of connected components of $G\setminus M$.

######  Lemma 21.

Let $H$ be a connected component of $G\setminus M$ of Type $A$ or $B$. Let
$\rho$ be the vertex of $P\cap H$. Then, for any vertex $v\in H$, there is no
shortest path between $v$ and $\rho$ using vertices in $G\setminus H$.
Moreover, for every $z\in\partial H$, there is a shortest path between $z$ and
$\rho$ using only vertices in $H\cup\\{z\\}$.

###### Proof.

Let $x$ and $y$ be the two vertices in $H$ adjacent to a vertex of $M$,
$\alpha$ be the vertex of $M$ adjacent to $x$ and $\beta$ the vertex in $M$
adjacent to $y$. By definition of _Types_ $A$ or $B$, $x\neq y$ (but $\alpha$
and $\beta$ could be the same vertex if the _Type_ is $B$).

By definition of $\rho$, we have $|d_{H}(x,\rho)-d_{H}(y,\rho)|\leq 1$. Let
$v\in V(H)$. Assume by contradiction that a shortest path between $v$ and
$\rho$ in $G$ passes through vertices in $G\setminus H$. So this shortest path
between $\rho$ and $v$ passes through $x$ and $y$. By symmetry we can assume
$d_{G}(v,\rho)=d_{H}(v,x)+d(x,\alpha)+d(\alpha,\beta)+d(\beta,y)+d_{H}(y,\rho)$.
In other words, the path from $v$ to $\rho$ passes through $x$ and then $y$.

Assume by contradiction that
$d_{H}(v,x)+d(x,\alpha)+d(\alpha,\beta)+d(\beta,y)+d_{H}(y,\rho)\leq
d_{G}(v,\rho)$. As $x\alpha$ and $y\beta$ are edges, we have
$d_{H}(v,x)+d(\alpha,\beta)+d_{H}(y,\rho)+2\leq d_{G}(v,\rho)$. By triangular
inequality, $d_{G}(v,\rho)\leq d_{H}(v,\rho)\leq d_{H}(v,x)+d_{H}(x,\rho)$. So
$d_{H}(x,\rho)\geq d_{H}(y,\rho)+d(\alpha,\beta)+2$ which contradicts
$|d_{H}(x,\rho)-d_{H}(y,\rho)|\leq 1$.

If $z$ is in $\partial H$ and $\alpha=\beta$ then $z=\alpha=\beta$ and the
result is immediate. Otherwise assume that $z=\alpha$. We want to contradict
$d(\alpha,\beta)+d(\beta,\rho)<d(\alpha,\rho)$. As $\alpha$ is adjacent to $x$
and $\beta$ adjacent to $y$ the inequality is equivalent to
$d(\alpha,\beta)+d(y,\rho)<d(x,\rho)$. As $\alpha\neq\beta$,
$d(\alpha,\beta)\geq 1$. So $d(y,\rho)+2\leq d(x,\rho)$ which contradicts
$|d_{H}(x,\rho)-d_{H}(y,\rho)|\leq 1$. ∎

We need one more definition to define our resolving set.

######  Definition 22.

Let $H$ be a connected component of $G\setminus M$ of Type $A$ or $B$ and let
$x$ and $y$ be the two vertices of $H$ adjacent to $M$. Let $u$ be any vertex
of $H$. The _projection $z_{u}$ of $u$ (on the path between $x$ and $y$)_ is
the unique vertex in the path between $x$ and $y$ in $H$ at minimum distance
to $u$.

We now have all the ingredients to define the set $S$ that will be a resolving
set based on resolving sets of each connected component $H$ of $G\setminus M$.
The union of the resolving sets of the different graphs is not a resolving set
for $G$, so we will need to add a few vertices. Moreover, the size of the
union of the resolving sets of the connected components of $G\setminus M$, is
not bounded by $L(G)+c$. Some vertices have to be removed from these resolving
sets.

Let $H$ be a connected component of $G\setminus M$. Let $S_{H}^{\prime}$ be a
metric basis for $H$ such that, for each major vertex of terminal degree at
least $2$ in $H$, all but one of its terminal vertices are in
$S_{H}^{\prime}$.

To get the announced bound we divided the component of _Type_ $B$ in two
parts. Let $H$ be a component of _Type_ $B$, $x$ and $y$ be the two vertices
of $H$ adjacent to a vertex of $M$. A component has type _Type_ $B_{1}$ if $x$
and $y$ are terminal vertices or exterior degree-two vertices. If $x$ (resp.
$y$) is a exterior degree-two vertex, $x$ (resp. $y$) lies on exactly one path
between a terminal vertex and a major vertex. Then, we define this terminal
vertex as the terminal vertex of $x$ (resp. $y$). If $x$ (resp. $y$) is a
terminal vertex, then $x$ (resp. $y$) is it own terminal vertex. A component
has _Type $B_{2}$_ if it is a component of _Type_ $B$ and not a component of
_Type_ $B_{1}$.

We define the set $S_{H}$ which is identical to $S_{H}^{\prime}$ but with the
following slight modifications:

  * •

$H$ has _Type_ $A$. For every $x\in H$ adjacent to $M$, if $x$ is a terminal
vertex and its major vertex $v$ in $H$ has terminal degree at least $2$, then,
if $x\in S_{H}^{\prime}$, remove $x$ from $S_{H}^{\prime}$, otherwise remove
from $S_{H}^{\prime}$ another terminal vertex of $x$.

  * •

$H$ has _Type_ $B_{1}$, we can assume that $S_{H}^{\prime}$ contains the two
terminal vertices of $x$ and $y$. Indeed, by Lemma 8, there exists a metric
basis of $H$ containing these two vertices.

  * •

$H$ has _Type_ $C$, let $x$ be the unique vertex of $H$ adjacent to $M$. If
$x$ is a terminal vertex and its major vertex $v$ in $H$ has terminal degree
at least $2$, then, if $x\in S_{H}^{\prime}$, remove $x$ from
$S_{H}^{\prime}$, otherwise remove from $S_{H}^{\prime}$ another terminal
vertex of $x$.

  * •

$H$ has _Type_ $C$ and $H$ is a path with one extremity adjacent to $M$. Let
$w$ be a vertex of $M$ adjacent to $H$. If there is only one component of
_Type_ C attached to $w$ that is a path connected to $w$ by an endpoint of the
path, let $S_{H}=\emptyset$. If there are several such components, then let
$S_{H}=\emptyset$ for one of these components and $S_{K}$ be the extremity of
the path not adjacent to $w$ for all the other such components $K$ (or the
unique vertex of $H$ if $H$ is reduced to a single vertex).

The set $S$ is defined as $S=M\cup P\cup(\bigcup_{i}S_{i})$. The goal will
consist in proving that $S$ is a resolving $S$.

###  3.2 The set $S$ is a resolving set

We will prove several lemmas that restrict the components where pairs of
unresolved vertices can belong to. Let us first prove that they must belong to
the same connected component of $G\setminus M$.

######  Lemma 23.

Let $u$ and $v$ be two vertices of $G$. If $u,v$ are not resolved by $S$ then
there exists a connected component of $H\in G\setminus M$ such that both $u,v$
belong to $H$.

###### Proof.

First note that since $M\subseteq S$, $u,v\notin M$. So there exist $H_{u}$
and $H_{v}$, connected components in $G\setminus M$, such that $u\in H_{u}$
and $v\in H_{v}$. Assume by contradiction that $H_{u}\neq H_{v}$.

  * •

Assume $H_{u}$ is of _Type_ $A$ or $B$ and let $x\alpha$ and $y\beta$ be the
two edges connecting $H_{u}$ to $M$ (with $x,y\in H_{u}$). Let $\rho$ be the
vertex in $P\cap H_{u}$. Since $v\notin H_{u}$, the shortest path between $v$
and $\rho$ passes through $\alpha$ or $\beta$. Up to symmetry, $\alpha$ is on
the shortest path between $v$ and $\rho$ so
$d(v,\rho)=d(v,\alpha)+d(\alpha,\rho)$. As $\alpha$ and $\rho$ are in $S$ we
also have $d(u,\rho)=d(u,\alpha)+d(\alpha,\rho)$, a contradiction with Lemma
21.

  * •

Assume now that both $H_{u}$ and $H_{v}$ are of _Type_ $C$. Let $\alpha$ and
$\beta$ be the vertices of $M$ connected to $H_{u}$ and $H_{v}$ respectively.
If $\alpha\neq\beta$, then the shortest path between $u$ and $v$ contains two
distinct vertices of $S$. Hence, by Lemma 10 $u$ and $v$ are resolved. We
assume now that $\alpha=\beta$.

Since all the components $H$ of _Type_ C attached to $\alpha$ but at most one
contain a vertex of $S_{H}$, by construction, $H_{u}$ or $H_{v}$ contains a
vertex of $S$. Without loss of generality, there exists $\gamma\in S\cap
H_{u}$. If $u$ is on the path between $\gamma$ and $v$ then
$d(\gamma,u)<d(\gamma,v)$. Otherwise, let $m_{u}$ in $H_{u}$ be at the
intersection of the path between $u$ and $\gamma$ and between $\alpha$ and
$\gamma$. Then, vertices $m_{u}$ and $\alpha$ are on the shortest path between
$u$ and $v$. By Lemma 10, one of them must resolve $u$ and $v$. By assumption,
it is not $\alpha$. If it is $m_{u}$, then we would have $d_{G}(u,\gamma)\neq
d_{G}(v,\gamma)$. Since the shortest paths between $u$, $v$ and $\gamma$ go
through $m_{u}$, we obtain a contradiction.

∎

We now prove that, if two vertices are in the same connected component of
$G\setminus M$, then they are resolved by $S$. We start with connected
components of _Type_ A.

######  Lemma 24.

Let $H$ be a connected component of $G\setminus M$ of Type A. Let $u$ and $v$
be two vertices of $H$ such that,for all $s$ in $S$, $d(u,s)=d(v,s)$. Then,
$z_{u}=z_{v}$.

###### Proof.

Let $u\alpha$ and $v\beta$ be the two edges between $H$ and $M$ with $u\in H$
and $v\in H$. The graph $H$ is a tree with a path between the two vertices $u$
and $v$. Assume $z_{u}\neq z_{v}$ and, without loss of generality, we can
suppose that $z_{u}\neq\rho$ with $\rho$ the vertex of $P\cap H$. We have
$d(u,\alpha)=d(u,z_{u})+d(z_{u},\alpha)$,
$d(v,\alpha)=d(v,z_{v})+d(z_{v},\alpha)$,
$d(u,\beta)=d(u,z_{u})+d(z_{u},\beta)$ and
$d(v,\beta)=d(v,z_{v})+d(z_{v},\beta)$. As $d(u,\alpha)=d(v,\alpha)$ and
$d(u,\beta)=d(v,\beta)$ we get

$d(z_{u},\alpha)+d(z_{v},\beta)=d(z_{u},\beta)+d(z_{v},\alpha).$

The vertices $z_{u}$ and $\rho$ are distinct and both between $\alpha$ and
$\beta$. So $z_{u}$ is between $\alpha$ and $\rho$ or $\beta$ and $\rho$.
Assume $z_{u}$ is between $\alpha$ and $\rho$. Then $d(z_{u},\alpha)\leq
d(z_{u},\beta)$, so $d(z_{v},\alpha)\leq d(z_{v},\beta)$ meaning $z_{v}$ is
also between $\alpha$ and $\rho$. The shortest path between $\alpha$ and
$\rho$ passes through $z_{u}$ and $z_{v}$ by Lemma 21. Assume $z_{u}$ is
closer than $z_{v}$ to $\rho$. Then
$d(\alpha,\rho)=d(\alpha,z_{v})+d(z_{v},z_{u})+d(z_{u},\rho)$ gives

$d(\alpha,z_{u})+d(z_{v},\rho)=d(\alpha,z_{v})+d(z_{u},\rho)+2d(z_{u},z_{v}).$

Use now the paths to $\rho$: $d(u,\rho)=d(u,z_{u})+d(z_{u},\rho)$ as
$z_{u}\neq\rho$ and $d(v,\rho)\leq d(v,z_{v})+d(z_{v},\rho)$. Then
$d(u,\alpha)=d(u,z_{u})+d(z_{u},\alpha)$,
$d(v,\alpha)=d(v,z_{v})+d(z_{v},\alpha)$ gives

$d(z_{v},\alpha)+d(z_{u},\rho)\leq d(z_{u},\alpha)+d(z_{v},\rho).$

A combination of the previous equality gives $d(z_{u},z_{v})\leq 0$ so
$z_{u}=z_{v}$. ∎

######  Lemma 25.

Let $H$ be a connected component of $G\setminus M$ of Type A. Let $u$ and $v$
be two vertices of $H$ such that, for all $s$ in $S$, $d(u,s)=d(v,s)$. Then
$u=v$.

###### Proof.

Assume by contradiction $u\neq v$. Let $\alpha$ and $\beta$ be the two
vertices of $M$ adjacent to $H$. By construction of $S_{H}$,
$S_{H}\cup\\{\alpha,\beta\\}$ is a resolving set of $H\cup\\{\alpha,\beta\\}$.
Let $\gamma$ which resolves the pair $(u,v)$ in $H\cup\\{\alpha,\beta\\}$. By
Lemma 24, $z_{u}=z_{v}$ so $\gamma$ still resolves $(u,v)$ in $G$. Indeed if
$z_{\gamma}=z_{u}$ then the distances are the same in $G$ and in
$H\cup\\{\alpha,\beta\\}$. If $z_{\gamma}\neq z_{u}$ then
$d_{G}(u,\gamma)=d_{H}(u,z_{u})+d_{G}(z_{u},\gamma)$ and
$d_{G}(v,\gamma)=d_{H}(v,z_{v})+d_{G}(z_{v},\gamma)$. As $d_{H}(u,\gamma)\neq
d_{H}(v,\gamma)$ with $d_{H}(u,\gamma)=d_{H}(u,z_{u})+d_{H}(z_{u},\gamma)$ and
$d_{H}(v,\gamma)=d_{H}(v,z_{u})+d_{H}(z_{u},\gamma)$ we get
$d_{H}(u,z_{u})\neq d_{H}(v,z_{u})$ so $d_{G}(u,\gamma)\neq d_{G}(v,\gamma)$.
So $\gamma$ resolves $(u,v)$ in $G$, a contradiction.

∎

######  Lemma 26.

Let $H$ be a connected component of $G\setminus M$ of Type B. If $u,v\in H$
are not resolved by $S$, then $z_{u}=z_{v}$.

###### Proof.

Let us prove it by contradiction. Let $\alpha$ be the vertex of $M$ connected
to $H$. Let $x,y$ be the two vertices of $H$ connected to $\alpha$.

Case 1: $H$ has _Type_ $B_{1}$
By construction, $\\{\alpha,\rho,y\\}\subseteq S$ with $y$ such that $z_{y}$
is connected to $\alpha$. Assume by contradiction $z_{u}\neq z_{v}$. We first
show that $(z_{u},z_{v})$ is resolved by $\\{\alpha,\rho,y\\}$. Indeed,
$d(y,z_{u})=d(y,z_{y})+d(z_{y},z_{u})$ and
$d(y,z_{v})=d(y,z_{y})+d(z_{y},z_{v})$. Lemma 12 ensures that $(z_{u},z_{v})$
is resolved by a vertex of $\\{\alpha,\rho,z_{y}\\}$ and if $z_{y}$ resolves
$(z_{u},z_{v})$, then $y$ resolves $(z_{u},z_{v})$. So $(z_{u},z_{v})$ is
resolved by a vertex of $\\{\alpha,\rho,y\\}$, let $\gamma$ be such a vertex.

If $z_{v}=\rho$, then $d(\gamma,u)=d(\gamma,z_{u})+d(z_{u},u)$ and
$d(\gamma,v)=d(\gamma,\rho)+d(\rho,v)$, so $d(z_{u},u)\neq d(\rho,v)$. As
$\rho\in S$, $d(u,\rho)=d(v,\rho)$ so $d(z_{u},u)<d(\rho,v)$. We exploit now
the equalities $d(\alpha,u)=d(\alpha,v)$ and
$d(\alpha,u)=d(\alpha,z_{u})+d(z_{u},u)$. By definition of $\rho$,
$d(\alpha,z_{u})\leq d(\alpha,\rho)$ and $d(z_{u},u)<d(\rho,v)$. So
$d(\alpha,v)=d(\alpha,\rho)+d(\rho,v)>d(\alpha,u)$, a contradiction.

If $z_{v}\neq\rho$, then $d(\gamma,u)=d(\gamma,z_{u})+d(u,z_{u})$ and
$d(\gamma,v)=d(\gamma,z_{v})+d(v,z_{v})$. By hypothesis
$d(\gamma,u)=d(\gamma,v)$, so $d(u,z_{u})\neq d(v,z_{v}).$ We can assume by
symmetry $d(z_{u},u)<d(z_{v},v)$. Let $\beta\in\\{\alpha,\rho\\}$, such that
$d(z_{u},\beta)\leq d(z_{v},\beta)$. Such a vertex exists since the distances
$d(\alpha,z_{u})+d(z_{u},\rho)$ and $d(\alpha,z_{v})+d(z_{v},\rho)$ are the
same if $z_{u},z_{v}$ are both on the same side of the $xy$-path with respect
to $\rho$ and differ by at most one otherwise. Then, $d(\beta,u)=d(\beta,v)$
and $d(\beta,u)=d(\beta,z_{u})+d(z_{u},u)$. But $d(\beta,z_{u})\leq
d(\beta,z_{v})$ and $d(z_{u},u)<d(z_{v},v)$. So
$d(\beta,v)=d(\beta,z_{v})+d(z_{v},v)>d(\beta,u)$, a contradiction.

Case 2: $H$ has _Type_ $B_{2}$
As $S$ contains $S_{H}$ which is a resolving set of $H$, there exists
$\gamma\in H$ such that $d_{H}(u,\gamma)\neq d_{H}(v,\gamma)$. By hypothesis
$d_{G}(u,\gamma)=d_{G}(v,\gamma)$.

Assume first $z_{\gamma}=\rho$. Let us prove that
$d_{G}(u,\gamma)=d_{H}(u,\gamma)$ and $d_{G}(v,\gamma)=d_{H}(v,\gamma)$, which
gives a contradiction. By symmetry it is enough to prove that
$d_{G}(u,\gamma)=d_{H}(u,\gamma)$. If $z_{u}=z_{\gamma}=\rho$ then
$d_{G}(u,\gamma)=d_{G}(u,\rho)+d_{G}(\rho,\gamma)=d_{H}(u,\rho)+d_{H}(\rho,\gamma)=d_{H}(u,\gamma)$
and the conclusion follows. If $z_{u}\neq z_{\gamma}$, then

$d_{G}(u,\gamma)=d_{G}(u,z_{u})+d_{G}(z_{u},\rho)+d_{G}(\rho,\gamma).$

By Lemma 21, $d_{G}(z_{u},\rho)=d_{H}(z_{u},\rho)$. We have
$d_{G}(u,z_{u})=d_{H}(u,z_{u})$ and $d_{G}(\rho,\gamma)=d_{H}(\rho,\gamma)$
since the paths between these vertices are unique. So
$d_{G}(u,\gamma)=d_{H}(u,\gamma)$.

So, from now on, we can assume that $z_{\gamma}\neq\rho$. Since
$\\{\rho,\alpha\\}$ does not resolve $(u,v)$, we have
$d(u,z_{u})+d(z_{u},\rho)=d(v,z_{v})+d(z_{v},\rho)$, and
$d(u,z_{u})+d(z_{u},\alpha)=d(v,z_{v})+d(z_{v},\alpha)$. Thus,

$d(z_{u},\rho)+d(z_{v},\alpha)=d(z_{v},\rho)+d(z_{u},\alpha).$

Since $\rho$ and $\alpha$ are almost opposed on the smallest cycle containing
them, we also have

$d(z_{u},\rho)+d(z_{u},\alpha)=d(z_{v},\rho)+d(z_{v},\alpha)+\epsilon$

with $\epsilon\in\\{-1,0,1\\}$. Summing the two equalities gives
$2d(z_{u},\rho)=2d(z_{v},\rho)+\epsilon$. So by parity $\epsilon=0$. Then,
$d(z_{u},\rho)=d(z_{v},\rho)$ and finally $d(z_{u},\alpha)=d(z_{v},\alpha)$.
Since $d(u,\alpha)=d(v,\alpha)$, we obtain $d(u,z_{u})=d(v,z_{v})$.

If $z_{\gamma}\notin\\{z_{u},z_{v}\\}$, then $z_{u}$ and $z_{v}$ are at the
same distance to $\alpha$, $\rho$ and $z_{\gamma}$, so, by Lemma 12,
$z_{u}=z_{v}$ . If $z_{\gamma}\in\\{z_{u},z_{v}\\}$, up to symmetry we can
assume $z_{\gamma}=z_{u}$. Then $d(u,\gamma)\leq d(u,z_{u})+d(z_{u},\gamma)$
and $d(v,\gamma)=d(v,z_{v})+d(z_{v},z_{u})+d(z_{u},\gamma)$. As
$d(u,\gamma)=d(v,\gamma)$ and $d(u,z_{u})=d(v,z_{v})$ we get
$d(z_{v},z_{u})\leq 0$ so $z_{u}=z_{v}$. ∎

######  Lemma 27.

Let $H$ be a connected component of $G\setminus M$ of Type B. The set $S$
resolves all the pairs of vertices of $H$.

###### Proof.

Let $u,v$ be two vertices of $H$ which are not resolved by $S$. By Lemma 26,
$z_{u}=z_{v}$. Let $z=z_{u}=z_{v}$, if $\deg(z)=2$ then $u=v=z$ and the result
is proven. We can assume from now on that $\deg(z)\geq 3$.

Case 1: There exists $\gamma\in S_{H}$ which resolves the pair $(u,v)$ in $H$.

If $z_{\gamma}=z_{u}=z_{v}$ then the distances between $u$ (resp. $v$) and
$\gamma$ are the same in $H$ and $G$, a contradiction.

So we can assume that $z_{\gamma}\neq z_{u}$. We have
$d_{H}(\gamma,u)=d_{H}(u,z)+d_{H}(z,\gamma)$ and
$d_{H}(\gamma,v)=d_{H}(v,z)+d_{H}(z,\gamma)$. Since $d_{H}(\gamma,u)\neq
d_{H}(\gamma,v)$, we have $d_{H}(u,z)\neq d_{H}(v,z)$. Now, since by Lemma 21,
for $w\in\\{u,v\\}$, $d_{H}(w,\rho)=d_{G}(w,\rho)$ and
$d(w,\rho)=d(w,z)+d(z,\rho)$, $\rho$ resolves $(u,v)$, a contradiction.

Case 2: The pair $(u,v)$ is not resolved by $S_{H}$ in $H$.

This case can only happen if $H$ has _Type_ $B_{1}$ (since otherwise no vertex
of $S_{H}^{\prime}$ is removed). Then there exists a vertex $x$ such that
$z_{x}$ is adjacent to $\alpha$ which resolves the pair $(u,v)$ in $H$. If
$z=z_{x}$, then, $d(z,u)=d(z,x)-d(u,x)$ and $d(z,v)=d(z,x)-d(v,x)$ so
$d(z,u)\neq d(z,v)$. If $z\neq x$ then $d(x,u)=d(x,z)+d(z,u)$ and
$d(x,v)=d(x,z)+d(z,v)$. So $d(z,u)\neq d(z,v)$ in both cases. Hence $\alpha$
resolves the pair $(u,v)$ in $G$. As $z\neq\alpha$,
$d(\alpha,u)=d(\alpha,z)+d(z,u)\neq d(\alpha,z)+d(z,v)=d(\alpha,v)$. ∎

######  Lemma 28.

Let $H$ be a connected component of $G\setminus M$ of Type C. Then $S$
resolves any pair of vertices in $H$.

###### Proof.

Assume by contradiction two vertices $u,v\in H$ with $u\neq v$ are not
resolved by $S$. Let $x$ be the unique vertex of $H$ adjacent to $M$ and $m$
be a vertex of $M$ adjacent to $x$. Let $H^{\prime}$ be the subgraph of $G$
with vertex set $V(H)\cup\\{m\\}$.

If $S$ contains a resolving set of $H$, then, since $x$ is a cut-vertex, $S$
resolves the pair $(u,v)$. So we can assume that at least one vertex of
$S_{H}^{\prime}$ has been removed during the construction of $S$.

Note that since $m$ does not resolve $(u,v)$, $d(u,x)=d(v,x)$ in $H$. So in
particular $H$ cannot be a path with endpoint $x$. So by construction of $S$,
we can assume that $x$ is a terminal vertex in $H$ and its major vertex has
terminal degree at least two in $H$.

By construction of $S_{H}$, $S\cup\\{x\\}$ is a resolving set for $H$. Then
$S\cup\\{m\\}$ is a resolving set for $H^{\prime}$. Let $\gamma\in
S_{H}\cup\\{m\\}$ that resolves $u$ and $v$ in $H^{\prime}$. The distances
between $u$, $v$ and $\gamma$ in $G$ and $H^{\prime}$ are the same so $\gamma$
resolves $u$ and $v$, a contradiction. ∎

######  Lemma 29.

The set $S$ is a resolving set of $G$.

###### Proof.

Let $(u,v)$ be a pair of vertices that is not resolved by $S$. Assume by
contradiction $u\neq v$. By Lemma 23, there exists a connected component $H$
of $G\setminus M$ such that $u\in H$ and $v\in H$. Then, if $H$ has _Type_ A,
by Lemma 25, $u=v$. If $H$ has _Type_ B, by Lemma 27, $u=v$. If $H$ has _Type_
C then, by Lemma 28, $u=v$. ∎

###  3.3 Upper bound on the size of $S$

Lemma 29 ensures that $\dim(G)\leq|S|$. So Theorem 1 holds if $|S|\leq
L(G)+6c$. The set $S$ is a union of three sets that we will bound the size
separately. We use the following result on minors to get the bounds.

Let $G$ be a multigraph. The graph $H$ is a minor of $G$ if $H$ can be
obtained from $G$ via a sequence of edge deletions, vertex deletions and edge
contractions (the edge contraction operation can create parallel edges between
two vertices or loops). One can easily check that the minor operation can only
decrease the cycle rank.

######  Lemma 30.

$|M|\leq 2c(G)-2$.

###### Proof.

If $|M|\leq 2$ then the inequality holds since we can assume $c\geq 2$. So we
can assume that $|M|\geq 3$. Let $K$ be the multigraph (with possible loops)
with vertex set $M$ where, for each connected component $H$ of $G\setminus M$
of _Type_ $A$ or $B$ with endpoints $x$ and $y$ in $M$ (that might be
identical), we create an edge between $x$ and $y$ in $K$. Note that $K$ is a
minor of $G$ as it can be obtained from $G$ by contracting edges in components
$H$ of $G\setminus M$ into a single edge.

Every vertex in $K$ has degree at least $3$. The vertices of $M\setminus X$
have degree at least $3$ by definition of $M_{i}$ for every $i$. By
construction of $X$, $x\in X$ has degree at least $3$ in the graph starting
from $G$ and removing the degree one vertices. Three adjacent edges belong to
cycles so contribute to the degree of $x$ in $K$ so $\deg_{K}(x)\geq 3$.

We have $3|V(K)|\leq\sum_{v\in V(K)}\deg(v)=2|E(K)|$. So $3|M|\leq 2|E|$.
Since the cycle rank of $K$ is at most $c$, so $|E|\leq c+|M|-1$. A
combination of these inequalities gives $|M|\leq 2c(G)-2$. ∎

######  Lemma 31.

$|P|\leq c+|M|-1$.

###### Proof.

Let $K^{\prime}$ be the multigraph (with loops) with vertex set $M$ and an
edge between two vertices $x$ and $y$ if and only if there exists in
$G\setminus M$ a connected component $H$ adjacent to $x$ and $y$. The graph
$K^{\prime}$ is a minor of $G$ since $K^{\prime}$ can be obtained from $G$ by
contracting edges with exactly one endpoint in $M$ until no such edge exists.
One can easily notice that in $K^{\prime}$ there is an edge $xy$ with
multiplicity $k$ if and only if in $G\setminus M$ there are $k$ connected
components attached to $x$ and $y$. Since $K^{\prime}$ is a minor of $G$,
$c(K^{\prime})\leq c(G)$. As $K^{\prime}$ contains $|M|$ vertices,
$K^{\prime}$ has at most $c+|M|-1$ edges. Thus, $G\setminus M$ has at most
$c+|M|-1$ components of _Type_ A or B. Since $P$ contains one vertex in each
component of _Type_ A or B, we have $|P|\leq c+|M|-1$. ∎

######  Lemma 32.

$\big{|}\bigcup_{H\text{con. comp. of }G\setminus M}S_{H}\big{|}\leq L(G)+c.$

###### Proof.

For every connected component $H$ of $G\setminus M$, let $\ell_{H}=\sum_{x\in
H}(ter(x)-1)$ over all the major vertices $x$ in $H$. We consider the three
types of components.

Let $H$ be a connected component of _Type_ $A$. We claim that
$|S_{H}|=\ell_{H}$. Indeed let $\epsilon\in\\{0,1,2\\}$ be the number of
vertices of $H$ adjacent to $M$ which are terminal vertices connected to a
major vertex of degree at least $2$. By construction
$L(H)-\epsilon=|S_{H}|=\dim(H)-\epsilon$.

Let $H$ be a connected component of _Type_ $B_{1}$. Then $L(H)=|S_{H}|+1$ and
$\ell_{H}=L(H)-2$ by construction so $|S_{H}|\leq\ell_{H}+1$.
Let $H$ be a connected component of _Type_ $B$ not $B_{1}$. Then,
$L(H)=|S_{H}|$ and $\ell_{H}\geq L(H)-1$ because $H$ has not _Type_ $B_{1}$ so
$|S_{H}|\leq\ell_{H}+1$.
Let $H$ be a component of _Type_ $C$ not a path. By construction of $S_{H}$,
$|S_{H}|=\ell_{H}$. Indeed, let $\epsilon\in\\{0,1\\}$ be the number of
vertices of $H$ adjacent to $M$ which are terminal vertices connected to a
major vertex of degree at least $2$. By construction
$|S_{H}|=\dim(H)-\epsilon=L(H)-\epsilon$ and $\ell_{H}=L(H)-\epsilon$.
Let $H$ be a component of _Type_ $C$ with $H$ a path. If $H$ is connected to
$M$ by a vertex $x$ which is not an extremity of $H$ then $m$ is a major
vertex of terminal degree 2 in $G$. So $|S_{H}|=\ell_{H}=1$. If $H$ is a path
connected to a vertex $m\in M$ by an extremity, let $k\in\mathbb{N}$ be the
number of such components connected to $m$. Denote them by
$H_{1},H_{2},...,H_{k}$. If $k\geq 2$ then $m$ is a major vertex in $G$ with
terminal degree $k$ and $|\cup_{i\leq
k}S_{H_{i}}|=k-1=|L(G)\cap\\{m\\}\cup(\cup_{i\leq k}H_{i})|$. If $k=1$ then
$S_{H}=\emptyset$ so $\ell_{H}=0$.
There are at most $c(G)$ components of _Type_ $B$: for each component $H$ of
_Type_ $B$ we can found a cycle in $G$ by adding the vertex of $M$ adjacent to
$H$. By definition of $c(G)$, this gives at most $c(G)$ components of _Type_
$B$. Summing the inequalities gives the result:

$|\cup S_{H}|=\sum_{\text{\emph{Type} $A$}}|S_{H}|+\sum_{\text{\emph{Type}
$B$}}|S_{H}|+\sum_{\text{\emph{Type} $C$}}|S_{H}|$
$\leq\sum_{\text{\emph{Type} $A$}}\ell_{H}+\sum_{\text{\emph{Type}
$B$}}(\ell_{H}+1)+\sum_{\text{\emph{Type} $C$}}\ell_{H}\leq L(G)+c(G)$

∎

Finally, we can prove Theorem 1:

###### Proof.

The set $S$ is a resolving set so $\dim(G)\leq|S|$. By definition $S=M\cup
P\cup(\bigcup_{H}S_{H})$. By Lemma 30, $|M|\leq 2c(G)$, by Lemma 31, $|P|\leq
3c$ and by Lemma 32, $|\cup S_{H}|\leq L(G)+c(G)$. Summing the inequalities
give $\dim(G)\leq L(G)+6c(G)$. ∎

Figure 10: Tightness of Lemmas 30, 31 and 32.

One can naturally ask if this upper bound is optimal. Figure 10 gives an
example of graph where Lemmas 30, 31 and 32 are tight. It ensures that our
analysis of the construction is optimal but not necessarily the construction
itself. Indeed, the metric dimension of the graph of Figure 10 is $8$ and the
square vertices form a metric basis.

##  4 Metric dimension and zero forcing sets

In this section, we study how the metric dimension and the zero forcing number
can be modified when an edge is added to a graph. Then we prove a weakening of
Conjecture 5, as a consequence of Theorem 1. We then give a short proof of
Conjecture 5 for unicyclic graphs. We will then generalize this result to
prove the conjecture for cactus graphs. We finally prove a strengthening of
Conjecture 5 when the graph is unicyclic and the unique cycle has odd length.

###  4.1 Edge modifications and consequences for Conjecture 5

The following lemma ensures that the variations of the zero forcing number
when an edge is added or deleted an edge are small [15].

######  Lemma 33.

[15] Let $G=(V,E)$ be a graph and $e\in E(G)$, then $Z(G)-1\leq Z(G-e)\leq
Z(G)+1$.

We have a more precise result if $Z(G+e)<Z(G)$ which will be useful later.

######  Lemma 34.

Let $G=(V,E)$ be a graph and $u$ and $v$ two vertices of $G$ such that
$e=uv\notin E$. If $Z(G+e)<Z(G)$, then for any minimum zero forcing set of
$G+e$, at some step $u$ forces $v$ or $v$ forces $u$.

###### Proof.

By contradiction if a zero forcing set of minimal size for $G+e$ does not use
the edge $e$ then it is a zero forcing set of $G$ so $Z(G)\leq Z(G+e)$. ∎

A similar statement does not hold for the metric dimension. However, Lemma 13
gives some conditions where a similar result holds. Using these results we can
get inequalities between the metric dimension and the zero forcing number for
some classes of graphs.

######  Corollary 35.

Let $G$ be a connected unicyclic graph and $e$ be an edge such that $T=G-e$ is
a tree. Then, $\dim(G)\leq Z(G)+2$.

###### Proof.

By Lemma 9, $\dim(T)\leq Z(T)$. Lemmas 13 and 33 ensure that $\dim(G)\leq
Z(G)+2$. ∎

Eroh et al. [8] proved Conjecture 5 for unicyclic graphs via a very long case
analysis. They start from a tree $T$ achieving $\dim(T)=Z(T)$ and make a
complete study of all the places where an edge could be added. We drastically
simplify their proof by starting from a unicyclic graph $G$ and delete a well-
chosen edge.

######  Lemma 36.

Let $G=(V,E)$ be a graph which is not a tree and $C\subseteq V$ a cycle of
$G$. Then, there exists an edge $e\in E(C)$ such that $Z(G-e)\leq Z(G)$.

###### Proof.

Let $Z\subseteq V$ be a minimum zero forcing set of $G$. Let $F\subseteq E$ be
the _forcing edges_ in a sequence starting from $Z$, i.e., $uv\in F$ if and
only if at some stage $u$ forces $v$ or $v$ forces $u$.

We claim that at least one edge of $C$ is not in $F$. Indeed, if $u$ forces
$v$ then $u$ is turned black before $v$. So, the first vertex $w$ of the cycle
that is turned black cannot be turned black because of an edge of $C$ (such a
vertex can already be black at the beginning of the proceed). Let
$w_{1},w_{2}$ be the two neighbors of $w$ on $C$. The vertex $w$ can force at
most one of its two neighbors. So, without loss of generality, $w_{2}$ is not
forced by $w$ and is turned black after $w$. So, if we remove the edge
$e=ww_{2}$, $Z$ is still a forcing set of $G-e$ with the same sequence of
applications of the color change rule that turned $G$ into black. Therefore,
$Z(G-e)\leq Z(G)$. ∎

We obtain as a corollary the main result of [8].

######  Corollary 37.

Let $G$ be a unicyclic graph. Then, $\dim(G)\leq Z(G)+1$.

###### Proof.

Let $e$ be an edge of $C$ such that $Z(G-e)\leq Z(G)$. Such an edge exists by
Lemma 36 and according to Lemma 13, $\dim(G)\leq\dim(G-e)+1$. Moreover, by
Lemma 9, $\dim(G-e)\leq Z(G-e)$ since $G-e$ is a tree. The combination of
these three inequalities gives $\dim(G)\leq Z(G)+1$. ∎

All these results together with Theorem 1 allow us to prove a weakening of
Conjecture 5 which we restate as follows:

See 6

###### Proof.

By induction with Lemma 36, there exists a spanning tree $T$ such that
$Z(T)\leq Z(G)$. By Lemma 9, $\dim(T)\leq Z(T)$ and thus, $\dim(G)\leq
Z(G)+6c(G)$ by Theorem 1. ∎

We generalize the proof of Conjecture 5 for unicyclic graphs to cactus graphs.
Almost the same techniques can be applied. First, we define the cactus graphs
class.

######  Definition 38.

Any graph $G$ is a cactus graph if any edge $e\in E(G)$ is part of at most one
cycle of $G$.

######  Theorem 39.

Let $G=(V,E)$ be a cactus graph. Then, $\dim(G)\leq c(G)+Z(G)$.

###### Proof.

We prove this inequality by induction on $c(G)$. If $c(G)=0$, then $G$ is a
tree and $\dim(G)\leq Z(G)$. If $c(G)>0$ let $C$ be a cycle of $G$. By Lemma
36, there exists an edge $e\in C$ such that $Z(G-e)\leq Z(G)$. By induction
$\dim(G-e)\leq Z(G-e)+c(G-e)\leq Z(G)+c(G-e)=Z(G)+c(G)-1$ since
$c(G-e)=c(G)-1$ for any $e\in C$.
To conclude, let us prove that Lemma 13 can be applied. Let
$v_{1},v_{2}...,v_{k}$ be the vertices of $C$. Let $G_{i}$ be the connected
component of $v_{i}$ in $G\setminus C$. Assume by contradiction that two
subgraphs $G_{i}$ and $G_{j}$ with $1\leq i<j\leq k$ are not disjoint. Then,
there exists a path $P$ between the vertices $v_{i}$ and $v_{j}$ in
$G\setminus C$. Then $G$ contains two cycles with common edges: $C$ and a
cycle containing $P$ and a path in $C$ between $v_{i}$ and $v_{j}$, a
contradiction. So, by Lemma 13, $\dim(G)\leq\dim(G-e)+1$ and then $\dim(G)\leq
c(G)+Z(G)$. ∎

As a corollary, we obtain that cactus graphs satisfy Conjecture 5. It improves
a result of [8] that ensures that $Z(G)\leq\dim(G)+2c(G)$ if $G$ has no even
cycles. If $G$ has no even cycles, all its cycles are edge disjoint. Indeed,
if two odd cycles share at least one edge then $G$ contains an even cycle.

###  4.2 Unicyclic graphs with an odd cycle

In this section, we consider the case where $G$ is unicyclic and its cycle has
odd length. In this case, we will improve the inequality of Corollary 37 to
get $\dim(G)\leq Z(G)$. Such a result cannot be extended to $G$ with an even
cycle, see Figure 6 for an example. The intuitive reason why there is a
difference between odd and even cycles is that, by Lemma 11, any pair of
vertices resolves an odd cycle while it is far from being true for even
cycles.

Before proving the main result of this section, we need some technical lemmas.
Let $k\geq 1$ and let $G=(V,E)$ be a graph containing a unique cycle $C$ of
length $2k+1$. For $u\in C$, let $T_{u}$ be the connected component of $u$ in
$G^{\prime}=(V,E\setminus E(C))$ rooted in $u$. Note that $T_{u}$ is a tree.
We call $u$ the root of $T_{u}$. We say that $T_{u}$ is _trivial_ if
$T_{u}=\\{u\\}$, is a _rooted path_ if $T_{u}$ is a path with $u$ at one
extremity and is a _rooted tree_ otherwise. Note that a rooted path can be
trivial (otherwise specified). For $u\in C$, if $T_{u}$ is not trivial we
denote by $\ell_{u}$ the terminal degree of $u$ in $G$. Else we let
$\ell_{u}=0$.

######  Lemma 40.

Let $G$ be an odd unicyclic graph. If there exists a vertex $u\in C$ such that
$\ell_{u}\geq 1$, then there is an edge $e\in E(C)$ incident to $u$ such that
$Z(G-e)\leq Z(G)$.

###### Proof.

By Lemma 34, it suffices to find a minimum zero forcing set for $G$ which does
not use one of the two edges in $E(C)$ incident to $u$. Let $Z$ be a minimum
zero forcing set of $G$. If $u\in Z$ then $u$ can force only one vertex and
the result is proved since at most one edge incident to $u$ is used. We can
assume $u\notin Z$. Let $P$ be an internal degree-two path between $u$ and a
terminal vertex $l$ of $G$ which exists since $\ell_{u}\geq 1$. If there is a
vertex $x$ in $P\cap Z$, then $(Z\setminus\\{x\\})\cup\\{l\\}$ is still a
minimum forcing set of $G$. Then, $l$ iteratively forces the vertices of $P$
until $u$ and we are back to the previous case. Finally, if $P$ and $u$ are
initially white, then $u$ is the first vertex of $P\cup\\{u\\}$ which is
turned black (eventually by one edge in $E(C)$). It then turns in black $P$.
We cannot use the second edge of $E(C)$ since every vertex forces at most one
vertex. ∎

######  Lemma 41.

Let $G$ be an odd unicyclic graph. Let $S\subseteq V(G)$ be such that for any
$u$ on the cycle, $S$ is not a subset of $T_{u}$. Then, $S$ resolves $C$.

###### Proof.

Let $\alpha$ and $\beta$ in $S$ such that $\alpha\in T_{u}$ and $\beta\in
T_{v}$ with $u\neq v$. Assume by contradiction that $x$ and $y$ in $C$
satisfies $d(x,\alpha)=d(y,\alpha)$ and $d(x,\beta)=d(y,\beta)$. Then, since
$d(x,\alpha)=d(x,u)+d(u,\alpha)$ and $d(y,\alpha)=d(y,u)+d(u,\alpha)$, we have
$d(x,u)=d(y,u)$. Similarly $d(x,v)=d(y,v)$, a contradiction with Lemma 11. ∎

######  Lemma 42.

Let $G$ be an odd unicyclic graph. If, for any $u\in V(C)$, $T_{u}$ is a
rooted tree, then for all $e\in E(C)$, $\dim(G)\leq\dim(G-e)$.

###### Proof.

Let $e\in E(C)$ and $S$ be a metric basis of $G-e$. In order to show that $S$
is still a resolving set of $G$, let us first prove that for every $u\in C$
since $T_{u}$ is a rooted tree $S\cap T_{u}\neq\emptyset$.

By definition of rooted tree, $T_{u}$ contains a vertex of degree $3$ in $G$.
Let $r$ be such a vertex. By Lemma 15, at most one connected component of
$G-e\setminus\\{r\\}$ does not contain element of $S$. The tree $T_{u}$
contains at least two connected components of $G-e\setminus\\{r\\}$, so $S\cap
T_{u}\neq\emptyset$.

Let $(x,y)$ be any pair of vertices. We prove that $S$ resolves $(x,y)$ in
$G$.

  1. 1.

Assume first that $x$ and $y$ are in the same component $T_{u}$ for some $u\in
C$. Let $\alpha\in S$ that resolves $(x,y)$ in $G-e$. If $\alpha\in T_{u}$
then $d_{G}(\alpha,x)=d_{G-e}(\alpha,x)\neq
d_{G-e}(\alpha,y)=d_{G}(\alpha,y)$.

We can assume that $\alpha\notin T_{u}$. Since $e\notin T_{u}$ and $u$ is a
cut-vertex of $G$ and $G-e$, we have $d_{G-e}(u,w)=d_{G}(u,w)$ for every $w\in
T_{u}$. For every $w\in T_{u}$,

$d_{G}(\alpha,w)=d_{G}(\alpha,u)+d_{G}(u,w)=d_{G}(\alpha,u)+d_{G-e}(u,w).$

Since $d_{G-e}(\alpha,w)=d_{G-e}(\alpha,u)+d_{G-e}(u,w)$ and
$d_{G-e}(\alpha,x)\neq d_{G-e}(\alpha,y)$, we have $d_{G-e}(u,x)\neq
d_{G-e}(u,y)$. Thus, $d_{G}(\alpha,x)\neq d_{G}(\alpha,y)$ and then $\alpha$
resolves $(x,y)$ in $G$.

  2. 2.

Suppose now $x$ and $y$ are in different components, respectively $T_{u}$ and
$T_{v}$. Then, there exist $\alpha\in S\cap T_{u}$ and $\beta\in S\cap T_{v}$.
Assume $d_{G}(\alpha,x)=d_{G}(\alpha,y)$ and $d_{G}(\beta,x)=d_{G}(\beta,y)$.
Then, $d_{G}(\alpha,x)\leq d_{G}(\alpha,u)+d_{G}(u,x)$ and
$d_{G}(\alpha,y)=d(\alpha,u)+d_{G}(u,v)+d_{G}(v,y)$ so
$d_{G}(u,v)+d_{G}(v,y)\leq d_{G}(u,x)$. The symmetric relation is
$d_{G}(v,u)+d_{G}(u,x)\leq d_{G}(v,y)$. Summing the two gives $2d_{G}(u,v)\leq
0$ which is a contradiction since $u\neq v$.∎

Next, we prove by case distinction the following result.

######  Theorem 43.

Any odd unicyclic graph $G$ satisfies $\dim(G)\leq Z(G)$.

###### Proof.

We make a case analysis on the structure of $G$ with $C$ being the unique
cycle of $G$.

Case 1: For every $u\in V(C)$, $T_{u}$ is a rooted tree.
By Lemma 36, there is an edge $e$ such that $Z(G-e)\leq Z(G)$. Since the $G-e$
is a tree, Corollary 9 ensures that $\dim(G-e)\leq Z(G-e)$. By Lemma 42,
$\dim(G)\leq\dim(G-e)$. The combination of these inequalities gives
$\dim(G)\leq Z(G)$.

Case 2: For every $u\in V(C)$, $T_{u}$ is a rooted path.
We prove that any pair of vertices $\alpha$ and $\beta$ of $C$ at distance $k$
is a resolving set of $G$.
Let ${\alpha,\beta}$ be such a pair of vertices. Let us first prove that for
every $x\in G$, $d(x,\alpha)+d(x,\beta)\in\\{k,k+1\\}$ if and only if $x\in
C$. Indeed as $d(\alpha,\beta)=k$ for any vertex $x$,
$d(x,\alpha)+d(x,\beta)\geq k$. If $x\in C$, then either $x$ is on the path
between $\alpha$ and $\beta$, and $d(x,\alpha)+d(x,\beta)=k$. Or $x$ is in the
other part of the cycle and $d(x,\alpha)+d(x,\beta)=k+1$. If $x\notin C$, then
let $y$ be the vertex of $C$ such that $x\in T_{y}$. Then,
$d(x,\alpha)+d(x,\beta)=d(y,\alpha)+d(y,\beta)+2d(x,y)\geq
2+d(y,\alpha)+d(y,\beta)\geq k+2$. This implies that a vertex on $C$ cannot
have the same distance vector as a vertex in $V\setminus C$.
By Lemma 41, the set $\\{\alpha,\beta\\}$ resolves $C$. To conclude we show
that $\\{\alpha,\beta\\}$ resolves $V\setminus C$. Let us prove that two
vertices not in $C$ are resolved. Assume by contradiction that two vertices
$x$ and $y$ are not resolved by $\\{\alpha,\beta\\}$, with $x\in T_{u}$ and
$y\in T_{v}$ for $u$ and $v$ in $C$. If $u=v$, since $T_{u}$ is a rooted path,
$\alpha$ resolves the pair $(x,y)$. From now on, we can assume that $u\neq v$.
Assume by symmetry $d(x,u)\leq d(y,v)$, and let $z\in T_{v}$ be the vertex on
$T_{v}$ such that $d(v,z)=d(x,u)$. Then, the pair $\\{\alpha,\beta\\}$ does
not resolve the pair $(z,u)$. But $u\in C$ and the previous cases ensures that
any pair of vertices with one vertex on $C$ is resolved by
$\\{\alpha,\beta\\}$, a contradiction. So $\dim(G)=2$ and $G$ is not a path,
so $Z(G)\geq 2$.

Case 3: There exists a unique $u\in V(C)$ such that $T_{u}$ is a rooted tree.
Let us prove that $\dim(G)\leq\dim(T_{u})+1$ and $Z(G)\geq Z(T_{u})+1$. Let
$S$ be a metric basis for $T_{u}$ and $v\in C$ a vertex at distance $k$ from
$u$.
Let us show that $S\cup\\{v\\}$ is a resolving set of $G$. Let $\alpha\in
S\cap T_{u}$, then $\\{\alpha,v\\}$ resolves $G\setminus T_{u}$. Indeed
otherwise, these two vertices would have the same distances to $u$ and $v$
which is impossible since in $G\setminus T_{u}$, for every $v\in C$, $T_{v}$
is a rooted path and by the claim in Case 2, $\\{u,v\\}$ is a resolving set
for $G\setminus(T_{u}\setminus\\{u\\})$. Two vertices on $T_{u}$ are resolved
since $S$ is a metric basis for $T_{u}$ and $u$ is a cut-vertex. Let $x\in
T_{w}$ for some $w\in C$, and $y\in T_{u}$. By triangular inequality,
$d(\alpha,y)\leq d(y,u)+d(u,\alpha)$. If $d(\alpha,y)=d(\alpha,x)$, then
$d(x,u)\leq d(y,u)$ as $d(\alpha,x)=d(\alpha,u)+d(u,x)$. If $d(x,v)=d(y,v)$,
then as $d(y,v)=d(y,u)+d(u,v)\geq d(x,u)+d(u,v)$. We get $d(x,v)\geq
d(x,u)+d(u,v)$. Removing $d(x,w)$ on both side gives $d(w,v)\geq
d(w,u)+d(u,v)$ which is impossible since $d(u,v)=k$ and $d(w,v)\leq k$. So $x$
and $y$ have different codes and $\dim(G)\leq\dim(T_{u})+1$.
Let $Z$ be a minimal zero forcing set of $G$. If $Z$ contains $u$, then it
should contain at least another vertex in $G\setminus T_{u}$. Since the
restriction of $Z$ to $T_{u}$ is a forcing set for $T_{u}$, we have $Z(G)\geq
Z(T_{u})+1$. So we can assume that $u\notin Z$. Consider a sequence of color
change rule that turns $u$ into black. Either $u$ is forced by a vertex in
$G\setminus T_{u}$. Since $(G\setminus T_{u})\cup\\{u\\}$ contains a cycle,
there are at least two vertices in $Z\cap(G\setminus T_{u})$ and $Z\cap
T_{u}\cup\\{u\\}$ is a forcing set of $T_{u}$. So $Z(G)\geq Z(T_{u})+1$.
Otherwise $u$ is forced by a vertex of $T_{u}$. Then, there is at least one
vertex in $Z\cap(G\setminus T_{u})$ and $Z\cap T_{u}$ is a forcing set of
$T_{u}$ so $Z(G)\geq Z(T_{u})+1$. So, $\dim(G)\leq\dim(T_{u})+1\leq
Z(T_{u})+1\leq Z(G)$.

For the remaining cases we use the following process: we exhibit an edge $e$
such that $Z(G-e)\leq Z(G)$ (by Lemma 36 or 40). Then, find a vertex $z$ in
$G-e$ such that $z$ is an interior degree-2 vertex or a major vertex with
terminal degree $0$ or $1$. By Lemma 8, $\dim(G-e)<Z(G-e)$ and by Lemma 13,
$\dim(G)\leq\dim(G-e)+1$, so $\dim(G)\leq Z(G)$. We just give the construction
of $e$ and $z$.

Case 4: There exists $u,v,w,x\in C$ in this order (not necessarily adjacent)
such that $T_{u}$ and $T_{w}$ are rooted trees and $T_{v}$ and $T_{x}$ are
rooted paths.
Let $e\in E(C)$ such that $Z(G-e)\leq Z(G)$. Such an edge exists by Lemma 36.
In $G-e$, either $v$ or $x$ is on the path between $u$ and $w$. Let $z$ be
this vertex, $z$ is an interior degree-2 vertex or a major vertex with
terminal degree $0$ or $1$ in $G-e$.

Case 5: There exist $u$ and $v$ adjacent with $T_{u}$ and $T_{v}$ rooted trees
and $w$ with $T_{w}$ a rooted path.

  * •

$l_{u}=0$. Let $e\in E(C)$ such that $Z(G-e)\leq Z(G)$. Such an edge exists by
Lemma 36. In $G-e$, $u$ is an interior degree-2 vertex or a major vertex with
terminal degree $0$ or $1$ so $z=u$.

  * •

$l_{u}=1$. Let $e\in E(C)$ adjacent to $u$ such that $Z(G-e)\leq Z(G)$. Such
an edge exists by Lemma 40. If $e=uv$ then $w$ is an interior degree-2 vertex
or a major vertex with terminal degree $0$ or $1$ in $G-e$ so $z=w$. If $e$ in
the other edge in $E(C)$ adjacent to $u$ then $u$ is an interior degree-2
vertex or a major vertex with terminal degree $0$ or $1$ in $G-e$ so $z=u$.

  * •

$l_{u}\geq 2$ and $l_{v}\geq 2$. Let $e=uv$, then $Z(G-e)\leq Z(G)$. Indeed a
minimal zero forcing set of $G$ is also a zero forcing set of $G-e$. Let $Z$
be a zero forcing set of $G$. The set $Z$ contains at least one terminal
vertex of $u$ and one terminal vertex of $v$. The terminal vertices can turn
black $u$ and $v$ so there is a sequence of forces for $G$ such that the edge
$e$ is not a forcing edge. So $Z(G-e)\leq Z(G)$ by Lemma 34. Then $w$ is an
interior degree-2 vertex or a major vertex with terminal degree $0$ or $1$ in
$G-e$ so $z=w$.

∎

## References

  * [1] Nicolas Bousquet, Quentin Deschamps, Aline Parreau and Ignacio M Pelayo  “On the cycle rank conjecture about metric dimension and zero forcing number in graphs”  In _Research Perspectives CRM Barcelona_ , 2021
  * [2] Peter J. Slater  “Leaves of trees”  In _Congressus Numerantium_ 14, 1975
  * [3] F. Harary and R.. Melter.  “On the metric dimension of a graph.”  In _Ars Combinatoria_ 2:191-195, 1975
  * [4] Garey and Johnson  “A Guide to the Theory of NP-completeness”  Journal of algorithms, 1979
  * [5] Josep Díaz, Olli Pottonen, Maria Serna and Erik Jan Van Leeuwen  “On the Complexity of Metric Dimension”  In _Algorithms – ESA 2012_ , 2012
  * [6] Samir Khuller, Balaji Raghavachari and Azriel Rosenfeld  “Landmarks in graphs”  In _Discrete Applied Mathematics_ 70.3, 1996, pp. 217–229
  * [7] Linda Eroh, Paul Feit, Cong X Kang and Eunjeong Yi  “The effect of vertex or edge deletion on the metric dimension of graphs”  In _J. Comb_ 6.4, 2015, pp. 433–444
  * [8] Linda Eroh, Cong X Kang and Eunjeong Yi  “A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs”  In _Acta Mathematica Sinica, English Series_ 33.6 Springer, 2017, pp. 731–747
  * [9] Gary Chartrand, Linda Eroh, Mark A. Johnson and Ortrud R. Oellermann  “Resolvability in graphs and the metric dimension of a graph”  In _Discrete Applied Mathematics_ 105.1, 2000, pp. 99–113
  * [10] Jelena Sedlar and Riste Škrekovski  “Vertex and edge metric dimensions of cacti”, 2021  arXiv:2107.01397 [math.CO]
  * [11] Jelena Sedlar and Riste Škrekovski  “Bounds on metric dimensions of graphs with edge disjoint cycles”  In _Applied Mathematics and Computation_ 396, 2021
  * [12] Special Graphs Work Group AIM  “Zero forcing sets and the minimum rank of graphs”  In _Linear Algebra and its Applications_ 428.7, 2008, pp. 1628–1648
  * [13] Maguy Trefois and Jean-Charles Delvenne  “Zero forcing number, constrained matchings and strong structural controllability”  In _Linear Algebra and its Applications_ 484, 2015, pp. 199–218
  * [14] Gary Chartrand, Linda Lesniak and Ping Zhang  “Graphs and Digraphs”  ChapmanHall/CRC, 2015
  * [15] Christina J. Edholm et al.  “Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph”  In _Linear Algebra and its Applications_ 436.12, 2012, pp. 4352–4372

##  Appendix A Proof of Lemma 13

The proof of this lemma in the paper of Eroh et al. [8] contains a flaw. We
present here a correction of the proof based on the same general ideas. See 13

Figure 11: The set $\\{\alpha,\beta,\gamma\\}$ resolves any pair of vertices
in two different circles

###### Proof.

Let $S$ be a metric basis of $G-e$ and $S_{i}=S\cap V_{i}$ for $1\leq i\leq
k$. Assume without loss of generality that $S_{1}\neq\emptyset$. If
$S_{i}=\emptyset$ for all $i\neq 1$, then $(G-e)\setminus G_{1}$ is a path and
$S_{1}\cup\\{u_{2}\\}$ is a resolving set of $G$. If there exists two non-
empty subsets $S_{i}$ and $S_{j}$ such that $d_{G}(u_{i},u_{j})=\frac{k}{2}$,
then let $\alpha_{0}\in V(C)\setminus\\{u_{i},u_{j}\\}$ and
$S_{0}=\\{\alpha_{0},\alpha_{i},\alpha_{j}\\}$ where $\alpha_{i}\in S_{i}$ and
$\alpha_{j}\in S_{j}$. Otherwise, let $i\neq 1$ be such that
$S_{i}\neq\emptyset$, let $\alpha_{0}=u_{\lfloor\frac{k}{2}\rfloor}$ and
$S_{0}=\\{\alpha_{0},\alpha_{i},\alpha_{1}\\}$ where $\alpha_{1}\in S_{1}$ and
$\alpha_{i}\in S_{i}$. Then, we prove that $S\cup\\{\alpha_{0}\\}$ is a
resolving set of $G$.
Let $v\in G_{i}$ and $w\in G_{j}$ with $i\neq j$ be two vertices in $G$. We
show that one vertex in $S_{0}$ resolves the pair $(u,v)$. For simplicity,
rename $S_{0}=\\{\alpha,\beta,\gamma\\}$ with $\alpha\in G_{\alpha}$,
$\beta\in G_{\beta}$ and $\gamma\in G_{\gamma}$ with
$d(u_{\alpha},u_{\beta})=\lfloor\frac{k}{2}\rfloor$ as in Figure 11.

Consider first the case where
$u_{v}\notin\\{u_{\alpha},u_{\beta},u_{\gamma}\\}$ and
$u_{w}\notin\\{u_{\alpha},u_{\beta},u_{\gamma}\\}$. Then, we have the
following equalities:

$d(v,\alpha)=d(w,\alpha)\text{ gives
}d(v,u_{v})+d(u_{v},u_{\alpha})+d(u_{\alpha},\alpha)=d(w,u_{w})+d(u_{w},u_{\alpha})+d(u_{\alpha},\alpha);$
$d(v,\beta)=d(w,\beta)\text{ gives
}d(v,u_{v})+d(u_{v},u_{\beta})+d(u_{\beta},\beta)=d(w,u_{w})+d(u_{w},u_{\beta})+d(u_{\beta},\beta);$
$d(v,\gamma)=d(w,\gamma)\text{ gives
}d(v,u_{v})+d(u_{v},u_{\gamma})+d(u_{\gamma},\gamma)=d(w,u_{w})+d(u_{w},u_{\gamma})+d(u_{\gamma},\gamma).$

Deleting the terms on the form $d(u_{\alpha},\alpha)$ and equalizing we get

$d(v,u_{v})-d(w,u_{w})=d(u_{w},u_{\alpha})-d(u_{v},u_{\alpha})=d(u_{w},u_{\beta})-d(u_{v},u_{\beta})=d(u_{w},u_{\gamma})-d(u_{v},u_{\gamma}).$

If $d(v,u_{v})-d(w,u_{w})=0$, then, by Lemma 12, $u_{v}=u_{w}$ as $u_{v}$ and
$u_{w}$ are at the same distance to three points on the cycle. Else, we have

$d(u_{\alpha},u_{w})+d(u_{w},u_{\beta})-d(u_{\alpha},u_{v})+d(u_{v},u_{\beta})=2(d(v,u_{v})-d(w,u_{w})),$

which is a contradiction as
$d(u_{\alpha},u_{\beta})=\lfloor\frac{k}{2}\rfloor$, the difference is in
$\\{-1,0,1\\}$. So we get $u_{v}=u_{w}$.

Consider now the case of one vertex $u_{v}$ or $u_{w}$ is equal to
$u_{\alpha}$ or $u_{\beta}$. Assume without loss of generality that
$u_{v}=u_{\alpha}$ and $u_{w}\neq u_{\alpha}$. Then $d(v,\alpha)\leq
d(v,u_{v})+d(u_{\alpha},\alpha)$ and as
$d(w,\alpha)=d(w,u_{w})+d(u_{w},u_{\alpha})+d(u_{\alpha},\alpha)$, we get:

$d(w,u_{w})+d(u_{w},u_{\alpha})\leq d(v,u_{v}).$

Consider now the distances to $\beta$:
$d(v,\beta)=d(v,u_{v})+\lfloor\frac{k}{2}\rfloor+d(u_{\beta},\beta)$ and
$d(w,\beta)\leq d(w,u_{w})+d(u_{w},u_{\beta})+d(u_{\beta},\beta)$. As
$d(v,\beta)=d(w,\beta)$:

$d(v,u_{v})+\lfloor\frac{k}{2}\rfloor\leq d(w,u_{w})+d(u_{w},u_{\beta}).$

Thus, $d(v,u_{v})\leq
d(w,u_{w})+d(u_{w},u_{\beta})-\lfloor\frac{k}{2}\rfloor$, and so

$d(u_{w},u_{\alpha})\leq d(u_{w},u_{\beta})-\lfloor\frac{k}{2}\rfloor.$

We assume $u_{w}\neq u_{\alpha}$ so $d(u_{w},u_{\alpha})\geq 1$ and
$d(u_{w},u_{\beta})\leq\lfloor\frac{k}{2}\rfloor$ by definition of $k$. We get
a contradiction as $d(u_{w},u_{\beta})\geq 0$.
The last case is $u_{v}=u_{\gamma}$ and
$u_{w}\notin\\{u_{\alpha},u_{\beta},u_{\gamma}\\}$. We have
$d(v,u_{v})+d(u_{v},u_{\alpha})=d(w,u_{w})+d(u_{w},u_{\alpha})$ and
$d(v,u_{v})+d(u_{v},u_{\beta})=d(w,u_{w})+d(u_{w},u_{\beta})$ and summing the
two equalities gives:

$2d(v,u_{v})+d(u_{v},u_{\alpha})+d(u_{v},u_{\beta})=2d(w,u_{w})+d(u_{w},u_{\alpha})+d(u_{w},u_{\beta}),$

which implies $d(v,u_{v})=d(w,u_{w})$. Then, by triangular inequality
$d(v,\gamma)\leq d(v,u_{v})+d(u_{\gamma},\gamma)$. Since
$d(v,\gamma)=d(w,\gamma)$, we get $d(w,u_{w})+d(u_{w},u_{\gamma})\leq
d(v,u_{v})$ and thus $d(u_{w},u_{\gamma})\leq 0$ which is a contradiction.
We proved that, if $v$ and $w$ are not in the same subgraph, then one vertex
in $S_{0}$ resolves them. So, if $v$ and $w$ are in $G_{i}$ for some $i$, by
definition of $S$, there exists $\mu\in S$ which resolve $(v,w)$ in $G-e$.
Hence, $\mu$ still resolves $(v,w)$ in $G$: If $\mu\in G_{i}$, then the
distances are the same in $G$ and in $G-e$. If $\mu\notin G_{i}$, then by
hypothesis $d_{G-e}(v,\mu)\neq d_{G-e}(w,\mu)$. By decomposition
$d_{G-e}(v,u_{v})+d_{G-e}(u_{v},\mu)\neq d_{G-e}(w,u_{w})+d_{G-e}(u_{w},\mu)$
so $d_{G-e}(v,u_{v})\neq d_{G-e}(w,u_{w})$. As
$d_{G-e}(v,u_{v})=d_{G}(v,u_{v})$ and $d_{G-e}(w,u_{w})=d_{G}(w,u_{w})$, we
get $d_{G}(v,u_{v})+d_{G}(u_{v},\mu)\neq d_{G}(w,u_{w})+d_{G}(u_{w},\mu)$. So
$\mu$ resolves $(v,w)$. Finally, $S\cup\\{\alpha_{0}\\}$ is a resolving set of
$G$, and so $\dim(G)\leq\dim(G-e)+1$.

∎