Nicolas Bousquet

Quentin Deschamps

Aline Parreau

Ignacio M Pelayo

Metric

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

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

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 distance to u and v uniquely identifies a vertex. This notion has been introduced in 1975 by Slater [START_REF] Peter | Leaves of trees[END_REF] for trees and by Harary and Melter [START_REF] Harary | On the metric dimension of a graph[END_REF] for graphs. Determining the minimum size of a resolving set, called metric dimension and denoted by dim(G), is an NPcomplete problem [START_REF] Garey | A Guide to the Theory of NP-completeness[END_REF] even restricted to planar graphs [START_REF] Díaz | On the Complexity of Metric Dimension[END_REF]. Applications of metric dimension goes from piloting a sonar [START_REF] Harary | On the metric dimension of a graph[END_REF] to the navigation of a robot in an Euclidean space [START_REF] Khuller | Landmarks in graphs[END_REF].

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 [START_REF] Eroh | The effect of vertex or edge deletion on the metric dimension of graphs[END_REF]), 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 Ω(n).

x 1

y 1 x 2 y 2 x k y k x 1 y 1 x 2 y 2 x k y k c 1 d 1 c 2 d 2 c k d k E 1 E 2 E k E 1 E 2 E k u u v e v
Figure 2: On the left graph, all the pairs (c i , d i ) are twins (both vertices have the same neighbourhood) so for all i ≤ k any resolving set should contain c i or d i . Then, for i ≤ 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 ≤ 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 ≤ 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 ≤ i ≤ k} is not resolving so the dimension is higher than k. The black vertices form a resolving set so the metric dimension is k + 1.

Metric dimension and cycle rank. Eroh et al. [START_REF] Eroh | A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs[END_REF] proved that, if G is a unicyclic graph, then the metric dimension of G is at most the metric dimension of any spanning tree 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 leaves are not in the resolving set and then these two vertices cannot be identified. 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. Chartrand et al. [START_REF] Chartrand | Resolvability in graphs and the metric dimension of a graph[END_REF] remarked that, for every connected graph G, dim(G) ≥ L(G) with equality for trees. However, this bound has no reason to be closed from the optimal value (a graph with no leaf can have an arbitrarily large metric dimension). A wheel (induced cycle plus a universal vertex), for instance, has no leaf 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) ≤ dim(G) ≤ 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. We have

dim(G) ≤ 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 ∈ 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) ≤ L(G) + 2c(G) ?

Note that Sedlar and Skrekovski independently ask the same question in [START_REF] Sedlar | Vertex and edge metric dimensions of cacti[END_REF]. The same authors also prove in [START_REF] Sedlar | Bounds on metric dimensions of graphs with edge disjoint cycles[END_REF] that Question 3 is true for cacti (and is 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 ≥ 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) ≤ dim(T ) + c? One can then wonder what happens if we select the best possible spanning tree to start with, i.e. the spanning that maximizes the metric dimension. In G k , one can note that if we break the edge 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 \ 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 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 [START_REF] Graphs | Zero forcing sets and the minimum rank of graphs[END_REF]. Deciding if the zero forcing number of a graph is at most k is NP-complete [START_REF] Trefois | Zero forcing number, constrained matchings and strong structural controllability[END_REF]. 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 [START_REF] Eroh | A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs[END_REF]. They proved that dim(G) ≤ Z(G) when G is a tree and that dim(G) ≤ 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 [START_REF] Eroh | A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs[END_REF]). For a connected graph dim(G) ≤ 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 Eroh et al. proved in [START_REF] Eroh | A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs[END_REF] that dim(G) ≤ 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

G 3 with c(G 3 ) = 3. Z(G) = c + 1 dim(G) = 2c + 1
dim(G) ≤ 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 ≥ 4 but the metric dimension is a linear function 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 Figure 5: The zero forcing number of a wheel is 3 (while n ≥ 4) but its metric dimension is linear in n.

proof than the one of [START_REF] Eroh | A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs[END_REF]. We then extend our results to prove Conjecture 5 for cactus graphs1 (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 [START_REF] Eroh | A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs[END_REF] on even cycle-free graphs. We finally show that dim(G) ≤ 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. 2 Preliminaries

dim(G) = 3 Z(G) = 2

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 [START_REF] Chartrand | Graphs and Digraphs. 6th. Chapman and Hall/CRC[END_REF]. Let G = (V, E) be a graph. The distance between two vertices u, v ∈ 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) = +∞. For v ∈ V , let N (v) be the (open) neighborhood of v defined as N (v) = {u ∈ V, uv ∈ E}. We say that two vertices v and w are twins if N (v) \ {w} = N (w) \ {v}. For X ⊆ 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 \ X the subgraph of G induced by V \ X. The border of X, denoted by ∂X, is {u ∈ G \ X| ∃v ∈ X, uv ∈ E}.

A vertex w ∈ V resolves a pair of vertices (u, v) if d(w, u) = d(w, v). Let S ⊆ 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 ⊆ 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 ⊆ 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 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 (or feedback edge set), denoted by c(G) (or c if the context is clear enough), is the minimum number of edges that should be deleted to 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 \ X is a forest. We denote by τ (G) (or τ if the context is clear enough) the minimum size of a feedback vertex set of G. Note that if X has minimum size, then τ (G) ≤ c(G).

Resolving sets and zero forcing sets on trees

Chartrand et al. [START_REF] Chartrand | Resolvability in graphs and the metric dimension of a graph[END_REF] 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.

Leaf Exterior major vertex

Interior major vertex

Exterior degree-two vertex Interior degree two vertex Let σ(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) = σ(G) -ex(G). We can bound dim(G) and Z(G) with this parameter:

Lemma 7. [8] For any connected graph G, dim(G) ≥ σ(G) -ex(G) and Z(G) ≥ L(G).
Lemma 8. [START_REF] Eroh | The effect of vertex or edge deletion on the metric dimension of graphs[END_REF] Let T be a tree which is not a path. Then, dim(T ) = L(T ). Moreover, any set containing all but exactly one terminal vertices of every major vertex is a resolving set of T .

There is no similar result to compute 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. [START_REF] Eroh | A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs[END_REF] For every tree T , dim(T ) ≤ 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.

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) = d(v, s) or d(u, t) = 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) = d(v, t) as t = 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 which 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 } such that for any i ≤ j d(v i , v j ) = min(j -i, k -j + i + 1) 2 , then, for any set S ⊆ 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 = 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 Assume now that a < y < b. If the shortest path between v 0 and v b passes through v y then

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 ,
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 = 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 [START_REF] Eroh | A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs[END_REF] 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 \ E(C). If, for every i = j, V i ∩ V j = ∅, then, for any e ∈ E(C), dim(G) ≤ dim(G -e) + 1.
The following lemma is a well-known fact about twins and resolving sets. Proof. Assume by contradiction that two connected components G i and G j of G \ {x} do not contain any vertex of S. Let v ∈ V and w ∈ V (G j ) be two vertices incident to u. Then, no vertex in S resolves the pair (v, w) since, for every s ∈ S, d(s, v) = d(s, w) = d(s, u) + 1.

Bounds for metric dimension

Definition 16. Let G be a graph. Recall that L(G) = σ(G) -ex(G). If G is a path P n for some n ≥ 1, let L(G) = 1 (so L(T ) = dim(T ) for all trees).
The goal is to prove Theorem 1 we recall here:

Theorem 1. For any graph G, L(G) ≤ dim(G) ≤ L(G) + 6c(G).
This result implies the following one:

Corollary 2.
Let G be a graph and T be any spanning tree of G. We have

dim(G) ≤ dim(T ) + 6c(G)
Proof. For any graph G = (V, E) that is not a tree and any edge e

∈ E such that G -e is connected, L(G) ≤ L(G -e). Indeed if a major vertex v has terminal degree d ≥ 2 in G, then v is still a major vertex in G -e of terminal degree at least d. So L(G) ≤ L(G -e) and then, for T a spanning tree of G, L(G) ≤ L(T ). As dim(G) ≤ L(G) + 6c(G) and dim(T ) = L(T ) we get dim(G) ≤ dim(T ) + 6c(G).
The rest of the section is devoted to prove Theorem 1. We now focus on the case c(G) ≥ 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 \ M is a forest such that each connected component has at most two edges incident to M . We then construct the set S.

Construction of the resolving set

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 τ (G) only containing vertices of degree at least 3.

Proof. Let X be a minimum feedback vertex set with the minimum number of vertices of degree 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 \ P . Let X = X \ {x} ∪ {z}. The set X 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 degree at least 3 in the graph where all the vertices of degree one have been iteratively removed 3 . Let G 1 , G 2 , ..., G k be the connected components of G \ X. Note that each G i induces a tree. For each G i , let X i ⊆ X be the set of vertices of X connected to at least one vertex of G i . Let N i ⊆ 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 ∈ N i . Let T i be the tree built from T i by adding to each vertex u ∈ N i , |N (u) ∩ X| pending leaves. Let M i be the set of vertices in T i of degree at least 3 and M := X ∪ ( k i=1 M i ). Figure 8 illustrates these notations. Proof. Let U H be the minimal subtree of H containing all the vertices incident to an edge between H and G \ H. Then, for each edge between a vertex v ∈ H and a vertex in G \ 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 leaves 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.

G i T i X N i M i
Let us prove by contradiction that if a vertex v has degree at least 3 in U H then this vertex should have been added in M .

Let i be such that H is a subgraph of G i and consider T i . Let P 1 , P 2 , P 3 be the three paths from v to M in U H which are internally disjoint, i.e. only v and possibly the endpoint in M are common. We claim that every vertex of M i can appear at most once since otherwise G i would contain a cycle. So for every path P i , we can complete P i into a path P i u 1 , u 2 , u 3 of H i from v to X such that the paths are internally disjoint. So v has degree at least 3 in T i , a contradiction. Let H be a connected component of G\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 ρ H be one vertex on the path in H between x and y such that |d H (x, ρ H ) -d H (y, ρ H )| ≤ 1. In other words, ρ H is one of the vertices in the middle of the path between x and y in H. Let P be the union of the vertices ρ H for all the connected components H of Type A and B.

(v, x) + d(α, β) + d H (y, ρ) + 2 ≤ d G (v, ρ). By triangular inequality, d G (v, ρ) ≤ d H (v, ρ) ≤ d H (v, x) + d H (x, ρ). So d H (x, ρ) ≥ d H (y, ρ) + d(α, β) + 2 which contradicts |d H (x, ρ) -d H (y, ρ)| ≤ 1.
If z is in ∂H and α = β then z = α = β and the result is immediate. Otherwise assume that z = α. We want to contradict d(α, β) + d(β, ρ) < d(α, ρ). As α is adjacent to x and β adjacent to y the inequality is equivalent to d(α, β)

+ d(y, ρ) < d(x, ρ). As α = β, d(α, β) ≥ 1. So d(y, ρ) + 2 ≤ d(x, ρ) which contradicts |d H (x, ρ) -d H (y, ρ)| ≤ 1.
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 \ 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 set of the connected components of G \ M , is not bounded by L(G) + c. Some vertices have to be removed of these resolving sets.

Let H be a connected component of G \ M . Let S H 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 leaves are in S H .

To get the announced bound we divided the component of Type B in two parts. A component has Type B 1 if it is a component of Type B and the two endpoints in H are the roots of a path in H and the major vertex of the leaf of the rooted path has terminal degree at least 2. 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 equal to S H but with the following slight modifications:

• H has Type A. For every x ∈ H adjacent to M , if x is a leaf and its terminal vertex v in H has degree at least 2, then, if x ∈ S H , remove x from S H , otherwise remove from S H another leaf associated to the terminal vertex of x.

• H has Type B 1 , we can assume that S H contains the two leaves x and y of H such that z x and z y are adjacent to M .

• H has Type C, let x be the unique vertex of H adjacent to M . If x is a leaf and its terminal vertex v in H has degree at least 2, then, if x ∈ S H , remove x from S H , otherwise remove from S H another leaf associated to the terminal vertex of x.

• H has Type C and H is a path with one extremity adjacent to M . Let w be the vertex of M adjacent to H. If there is only one component of Type C attached to w which is a path connected to w by an endpoint of the path, let S H = ∅. If there are several such components, then let S H = ∅ for one of these components and S K be the extremity of the path not connected 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 ∪ P ∪ ( i S i ). The goal will consist in proving that S is a resolving S.

The set S is a resolving set

Before proving the main result of this section, we start with a definition. Definition 22. Let H be a connected component of G \ M of Type A or B and let x and y be the two vertices in 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 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 \ 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 ∈ G \ M such that both u, v belong to H.

Proof. First note that since M ⊆ S, u, v / ∈ M . So there exist H u and H v , connected components in G \ M , such that u ∈ H u and v ∈ H v . Assume by contradiction that H u = H v .

• Assume H u is of Type A or B and let xα and yβ be the two edges connecting H u to M (with x, y ∈ H u ). Let ρ be the vertex in P ∩ H u . Since v / ∈ H u , the shortest path between v and ρ passes through α or β. Up to symmetry, α is on the shortest path between v and ρ so d(v, ρ) = d(v, α) + d(α, ρ). As α and ρ are in S we also have d(u, ρ) = d(u, α) + d(α, ρ), a contradiction with Lemma 21.

• Assume now that both H u and H v are of Type C. Let α and β the vertices of M connected to H u and H v respectively. If α = β, 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 α = β.

Since all the components H of Type C attached to α 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 γ ∈ S ∩ H u . If u is on the path between γ and v then d(γ, u) < d(γ, v). Otherwise, let m u in H u be at the intersection of the path between u and γ and between α and γ. Then, vertices m u and α 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 α. If it is m u , then we would have

d G (u, γ) = d G (v, γ).
Since the shortest paths between u, v and γ go through m u , we obtain a contradiction.

We now prove that, if two vertices are in the same connected component of G \ 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 \ 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α and vβ be the two edges between H and M with u ∈ H and v ∈ H. The graph H is a tree with a path between the two vertices u and v. Assume z u = z v and, without loss of generality, we can suppose that z u = ρ with ρ the vertex of P ∩ H. We have

d(u, α) = d(u, z u ) + d(z u , α), d(v, α) = d(v, z v ) + d(z v , α), d(u, β) = d(u, z u ) + d(z u , β) and d(v, β) = d(v, z v ) + d(z v , β). As d(u, α) = d(v, α) and d(u, β) = d(v, β) we get d(z u , α) + d(z v , β) = d(z u , β) + d(z v , α).
The vertices z u and ρ are distinct and both between α and β. So z u is between α and ρ or β and ρ. Assume z u is between α and ρ. Then d(z u , α) ≤ d(z u , β), so d(z v , α) ≤ d(z v , β) meaning z v is also between α and ρ. The shortest path between α and ρ passes through z u and z v by Lemma 21. Assume z u is closer than

z v to ρ. Then d(α, ρ) = d(α, z v ) + d(z v , z u ) + d(z u , ρ) gives d(α, z u ) + d(z v , ρ) = d(α, z v ) + d(z u , ρ) + 2d(z u , z v ).

Use now the paths to

ρ: d(u, ρ) = d(u, z u ) + d(z u , ρ) as z u = ρ and d(v, ρ) ≤ d(v, z v ) + d(z v , ρ). Then d(u, α) = d(u, z u ) + d(z u , α), d(v, α) = d(v, z v ) + d(z v , α) gives d(z v , α) + d(z u , ρ) ≤ d(z u , α) + d(z v , ρ).

A combination of the previous equality gives

d(z u , z v ) ≤ 0 so z u = z v .
Lemma 25. Let H be a connected component of G \ 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 = v. Let α and β be the two vertices of M adjacent to H. By construction of S H , S H ∪{α, β} is a resolving set of H ∪{α, β}. Let γ which resolves the pair (u, v) in H ∪ {α, β}. By Lemma 24, z u = z v so γ still resolves (u, v) in G. Indeed if z γ = z u then the distances are the same in G and in H ∪{α, β}.

If z γ = z u then d G (u, γ) = d H (u, z u )+d G (z u , γ) and d G (v, γ) = d H (v, z v ) + d G (z v , γ). As d H (u, γ) = d H (v, γ) with d H (u, γ) = d H (u, z u ) + d H (z u , γ) and d H (v, γ) = d H (v, z u ) + d H (z u , γ) we get d H (u, z u ) = d H (v, z u ) so d G (u, γ) = d G (v, γ). So γ resolves (u, v) in G, a contradiction. Lemma 26. Let H be a connected component of G \ M of Type B. If u, v ∈ H are not resolved by S, then z u = z v .
Proof. Let us prove it by contradiction. Let α be the vertex of M connected to H. Let x, y be the two vertices of H connected to α. Case 1: H has Type B 1 By construction, {α, ρ, y} ⊆ S with y such that z y is connected to α. Assume by contradiction z u = z v . We first show that (z u , z v ) is resolved by {α, ρ, 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 {α, ρ, 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 {α, ρ, y}, let γ be such a vertex.

If

z v = ρ, then d(γ, u) = d(γ, z u ) + d(z u , u) and d(γ, v) = d(γ, ρ) + d(ρ, v), so d(z u , u) = d(ρ, v). As ρ ∈ S, d(u, ρ) = d(v, ρ) so d(z u , u) < d(ρ, v). We exploit now the equalities d(α, u) = d(α, v) and d(α, u) = d(α, z u ) + d(z u , u). By definition of ρ, d(α, z u ) ≤ d(α, ρ) and d(z u , u) < d(ρ, v). So d(α, v) = d(α, ρ) + d(ρ, v) > d(α, u), a contradiction. If z v = ρ, then d(γ, u) = d(γ, z u ) + d(u, z u ) and d(γ, v) = d(γ, z v ) + d(v, z v ). By hypothesis d(γ, u) = d(γ, v), so d(u, z u ) = d(v, z v ). We can assume by symmetry d(z u , u) < d(z v , v). Let β ∈ {α, ρ}, such that d(z u , β) ≤ d(z v , β
). Such a vertex exists since the distances d(α, z u )+d(z u , ρ) and d(α, z v ) + d(z v , ρ) are the same if z u , z v are both on the same side of the xy-path with respect to ρ and differ by at most one otherwise. Then,

d(β, u) = d(β, v) and d(β, u) = d(β, z u ) + d(z u , u). But d(β, z u ) ≤ d(β, z v ) and d(z u , u) < d(z v , v). So d(β, v) = d(β, z v ) + d(z v , v) > d(β, u), a contradiction. Case 2: H has Type B 2 As S contains S H which is a resolving set of H, there exists γ ∈ H such that d H (u, γ) = d H (v, γ). By hypothesis d G (u, γ) = d G (v, γ). Assume first z γ = ρ. Let us prove that d G (u, γ) = d H (u, γ) and d G (v, γ) = d H (v, γ), which gives a contradiction. By symmetry it is enough to prove that d G (u, γ) = d H (u, γ). If z u = z γ = ρ then d G (u, γ) = d G (u, ρ) + d G (ρ, γ) = d H (u, ρ) + d H (ρ, γ) = d H (u, γ) and the conclusion follows. If z u = z γ , then d G (u, γ) = d G (u, z u ) + d G (z u , ρ) + d G (ρ, γ). By Lemma 21, d G (z u , ρ) = d H (z u , ρ). We have d G (u, z u ) = d H (u, z u ) and d G (ρ, γ) = d H (ρ, γ) since the paths between these vertices are unique. So d G (u, γ) = d H (u, γ).
So, from now on, we can assume that z γ = ρ. Since {ρ, α} does not resolve (u, v), we have

d(u, z u ) + d(z u , ρ) = d(v, z v ) + d(z v , ρ), and d(u, z u ) + d(z u , α) = d(v, z v ) + d(z v , α). Thus, d(z u , ρ) + d(z v , α) = d(z v , ρ) + d(z u , α).
Since ρ and α are almost opposed on the smallest cycle containing them, we also have

d(z u , ρ) + d(z u , α) = d(z v , ρ) + d(z v , α) + with ∈ {-1, 0, 1}. Summing the two equalities gives 2d(z u , ρ) = 2d(z v , ρ) + . So by parity = 0. Then, d(z u , ρ) = d(z v , ρ) and finally d(z u , α) = d(z v , α). Since d(u, α) = d(v, α), we obtain d(u, z u ) = d(v, z v ).
If z γ / ∈ {z u , z v }, then z u and z v are at the same distance to α, ρ and z γ , so, by Lemma 12,

z u = z v . If z γ ∈ {z u , z v }, up to symmetry we can assume z γ = z u . Then d(u, γ) ≤ d(u, z u ) + d(z u , γ) and d(v, γ) = d(v, z v ) + d(z v , z u ) + d(z u , γ). As d(u, γ) = d(v, γ) and d(u, z u ) = d(v, z v ) we get d(z v , z u ) ≤ 0 so z u = z v .
Lemma 27. Let H be a connected component of G \ 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) ≥ 3. Case 1: There exists γ ∈ S H which resolves the pair (u, v) in H.

If z γ = z u = z v then the distances between u (resp. v) and γ are the same in H and G, a contradiction.

So we can assume that z γ = z u . We have

d H (γ, u) = d H (u, z) + d H (z, γ) and d H (γ, v) = d H (v, z) + d H (z, γ). Since d H (γ, u) = d H (γ, v), we have d H (u, z) = d H (v, z). Now, since by Lemma 21, for w ∈ {u, v}, d H (w, ρ) = d G (w, ρ) and d(w, ρ) = d(w, z) + d(z, ρ), ρ 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 is removed). Then there exists a vertex x such that z x is adjacent to α 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) = d(z, v). If z = 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) = d(z, v) in both cases. Hence α resolves the pair (u, v) in G. As z = α, d(α, u) = d(α, z) + d(z, u) = d(α, z) + d(z, v) = d(α, v).
Lemma 28. Let H be a connected component of G \ M of Type C. Then S resolves any pair of vertices in H.

Proof. Assume by contradiction two vertices u, v ∈ H with u = 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 be the subgraph of G with vertex set V (H) ∪ {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 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 leaf in H and its major vertex has terminal degree at least two in H.

By construction of S H , S ∪ {x} is a resolving set for H. Then S ∪ {m} is a resolving set for H . Let γ ∈ S H ∪ {m} that resolves u and v in H . The distances between u, v and γ in G and H are the same so γ resolves u and v, a contradiction.

Upper bound on the size of S

Lemma 29 ensures that dim(G) ≤ |S|. So Theorem 1 holds if |S| ≤ 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 | ≤ 2c(G) -2.
Proof. If |M | ≤ 2 then the inequality holds since we can assume c ≥ 2. So we can assume that |M | ≥ 3. Let K be the multigraph (with possible loops) with vertex set M where, for each connected component H of G \ 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 \ M into a single edge.

Every vertex in K has degree at least 3. The vertices of M \ X have degree at least 3 by definition of M i for every i. By construction of X, x ∈ 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) ≥ 3.

We have

3|V (K)| ≤ v∈V (K) deg(v) = 2|E(K)|. So 3|M | ≤ 2|E|. Since the cycle rank of K is at most c, so |E| ≤ c + |M | -1. A combination of these inequalities gives |M | ≤ 2c(G) -2. Lemma 31. |P | ≤ c + |M | -1.
Proof. Let K 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 \ M a connected component H adjacent to x and y. The graph K is a minor of G since K 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 there is an edge xy with multiplicity k if and only if in G \ M there are k connected components attached to x and y. Since K is a minor of G, c(K ) ≤ c(G). 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.

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.

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 [START_REF] Edholm | Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph[END_REF].

Lemma 33. [15] Let G = (V, E) be a graph and e ∈ E(G), then Z(G) -1 ≤ Z(G -e) ≤ Z(G) + 1. |X| = c |M | = 2c -2 X M P |P | = |M | + c -1
A minimal resolving set 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 / ∈ 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) ≤ Z(G + e).

A similar statement does not hold for 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. We have dim(G) ≤ Z(G) + 2.

Proof. By Lemma 9, dim(T ) ≤ Z(T ). Lemmas 13 and 33 ensure that dim(G) ≤ Z(G) + 2.

Eroh et al. [START_REF] Eroh | A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs[END_REF] 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 ⊆ V a cycle of G. Then, there exists an edge e ∈ E(C) such that Z(G -e) ≤ Z(G).

Proof. Let Z ⊆ V be a minimum zero forcing set of G. Let F ⊆ E be the forcing edges in a sequence starting from Z, i.e. uv ∈ 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) ≤ Z(G). This implies that a vertex on C cannot have the same distance vector as a vertex in V \ C. By Lemma 41, the set {α, β} resolves C. To conclude we have to show that {α, β} resolves V \ 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 {α, β}, with x ∈ T u and y ∈ T v for u and v in C. If u = v, since T u is a rooted path, α resolves the pair (x, y). From now on, we can assume that u = v. Assume by symmetry d(x, u) ≤ d(y, v), and let z ∈ T v be the vertex on T v such that d(v, z) = d(x, u). Then, the pair {α, β} does not resolve the pair (z, u). But u ∈ C and the previous cases ensures that any pair of vertices with one vertex on C is resolved by {α, β}, a contradiction. So dim(G) = 2 and G is not a path, so Z(G) ≥ 2.

Case 3: There exists a unique u ∈ C such that T u is a rooted tree. Let us prove that dim(G) ≤ dim(T u ) + 1 and Z(G) ≥ Z(T u ) + 1. Let S be a metric basis for T u and v ∈ C a vertex at distance k from u. Let us show that S ∪ {v} is a resolving set of G. Let α ∈ S ∩T u , then {α, v} resolves G\T u . Indeed otherwise, these two vertices would have the same distances to u and v which is impossible since in G \ T u , for every v ∈ C, T v is a rooted path and by the claim in Case 2, {u, v} is a resolving set for G\(T u \{u}). Two vertices on T u are resolved since S is a metric basis for T u and u is a cut-vertex. Let Z be a minimal zero forcing set of G. If Z contains u, then it should contain at least another vertex in G \ T u . Since the restriction of Z to T u is a forcing set for T u , we have Z(G) ≥ Z(T u ) + 1. So we can assume that u / ∈ Z. Consider a sequence of color change rule that turns u into black. Either u is forced by a vertex in G \ T u . Since (G \ T u ) ∪ {u} contains a cycle, there are at least two vertices in Z ∩ (G \ T u ) and Z ∩ T u ∪ {u} is a forcing set of T u . So Z(G) ≥ Z(T u ) + 1. Otherwise u is forced by a vertex of T u . Then there is at least one vertex in Z ∩ (G \ T u ) and Z ∩ T u is a forcing set of T u so Z(G) ≥ Z(T u )+1. So in both cases we have dim(G) ≤ dim(T u )+1 ≤ Z(T u )+1 ≤ Z(G).

For the other cases we use the following process: we exhibit an edge e such that Z(G-e) ≤ 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) ≤ dim(G-e)+1, so dim(G) ≤ Z(G). We just give the construction of e and z.

Case 4: There exists u, v, w, x ∈ 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 ∈ E(C) such that Z(G -e) ≤ Z(G). Such an edge exists by Lemma 36. In G -e, either the vertex 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 ∈ E(C) such that Z(G -e) ≤ 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 ∈ E(C) adjacent to u such that Z(G -e) ≤ 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 ≥ 2 and l v ≥ 2. Let e = uv, then Z(G -e) ≤ 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 leaf of u and one leaf of v. The leaves 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) ≤ 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.

Figure 1 :

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

Figure 3 :

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

Figure 4 :

 4 Figure 4: Tightness of Conjecture 5

Figure 6 :

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

Figure 7 :

 7 Figure 7: Vertices denomination in a graph

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

Lemma 14 .

 14 Let u and v be two twins of a graph G. Any resolving set S of G verifies S∩{u, v} = ∅.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 \ {u} does not contain any vertex of S.

  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) ≤ 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) ≤ dim(T ) + 1 by Lemma 13. As L(T ) ≤ L(G) + 2 we get the inequality.

Figure 8 :

 8 Figure 8: Illustration of the notations X, N i , M i , T i and G i .

  Lemma 19 indeed implies the following.Corollary 20. Every connected component of G \ M is connected to at most two vertices of M .A connected component of G \ M can be attached to M in three different ways, called Types, illustrated in Figure9. A connected component of G \ 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 ).

Figure 9 :

 9 Figure 9: The three Types of connected components of G \ M .

Lemma 29 .

 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 = v. By Lemma 23, there exists a connected component H of G \ M such that u ∈ H and v ∈ 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.

  As K contains |M | vertices, K has at most c + |M | -1 edges. Thus, G \ 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 | ≤ c + |M | -1.Lemma 32.Hcon. comp. of G\M S H ≤ L(G) + c.Proof. For every connected component H of G \ M , let H = x∈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 | = H . Indeed let ∈ {0, 1, 2} be the number of vertices of H adjacent to M which are leaf connected to a major vertex of degree at least 2. By constructionL(H) -= |S H | = dim(H) -. Let H be a connected component of Type B 1 . Then L(H) = |S H | + 1 and H = L(H) -2 by construction so |S H | ≤ H + 1. Let H be a connected component of Type B not B 1 . Then, L(H) = |S H | and H ≥ L(H) -1 because H has not Type B 1 so |S H | ≤ H + 1. Let H be a component of Type C not a path. By construction of S H , |S H | = H . Indeed, let∈ {0, 1} be the number of vertices of H adjacent to M which are leaves connected to a major vertex of degree at least 2. By construction|S H | = dim(H) -= L(H) -and H = L(H) -.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 | = H = 1.If H is a path connected to a vertex m ∈ M by an extremity, let k ∈ N be the number of such components connected to m. Denote them byH 1 , H 2 , ..., H k . If k ≥ 2 then m is a major vertex in G with terminal degree k and | ∪ i≤k S Hi | = k -1 = |L(G) ∩ {m} ∪ (∪ i≤k H i )|. If k = 1 then S H = ∅ so 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: | ∪ S H | = (G) + c(G) Finally, we can prove Theorem 1: Proof. The set S is a resolving set so dim(G) ≤ |S|. By definition S = M ∪ P ∪ ( H S H ). By Lemma 30, |M | ≤ 2c(G), by Lemma 31, |P | ≤ 3c and by Lemma 32,| ∪ S H | ≤ L(G) + c(G). Summing the inequalities give dim(G) ≤ L(G) + 6c(G).

Figure 10 :

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

Case 2 :

 2 For every u ∈ C, T u is a rooted path. We prove that any pair of vertices α and β of C at distance k is a resolving set of G. Let α, β be such a pair of vertices. Let us first prove that for every x ∈ G, d(x, α) + d(x, β) ∈ {k, k + 1} if and only if x ∈ C. Indeed as d(α, β) = k for any vertex x, d(x, α) + d(x, β) ≥ k. If x ∈ C, then either x is on the path between α and β, and d(x, α) + d(x, β) = k. Or x is in the other part of the cycle and d(x, α) + d(x, β) = k + 1. If x / ∈ C, then let y be the vertex of C such that x ∈ T y . Then, d(x, α) + d(x, β) = d(y, α) + d(y, β) + 2d(x, y) ≥ 2 + d(y, α) + d(y, β) ≥ k + 2.

  Let x ∈ T w for some w ∈ C, and y ∈ T u . By triangular inequality, d(α, y) ≤ d(y, u) + d(u, α). If d(α, y) = d(α, x), then d(x, u) ≤ d(y, u) as d(α, x) = d(α, u) + d(u, x). If d(x, v) = d(y, v), then as d(y, v) = d(y, u) + d(u, v) ≥ d(x, u) + d(u, v). We get d(x, v) ≥ d(x, u) + d(u, v). Removing d(x, w) on both side gives d(w, v) ≥ d(w, u) + d(u, v) which is impossible since d(u, v) = k and d(w, v) ≤ k. So x and y have different codes and dim(G) ≤ dim(T u ) + 1.

This result is proved independently in[START_REF] Sedlar | Vertex and edge metric dimensions of cacti[END_REF] with a different method.

This condition ensures that there is no shortcut between the vertices of C.

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

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

We obtain as a corollary the main result of [START_REF] Eroh | A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs[END_REF].

Corollary 37. Let G be a unicyclic graph. Then, dim(G) ≤ Z(G) + 1.

Proof. Let e be an edge of C such that Z(G -e) ≤ Z(G). Such an edge exists by Lemma 36. By Lemma 13, dim(G) ≤ dim(G -e) + 1. Moreover, by Lemma 9, dim(G -e) ≤ Z(G -e) since G -e is a tree. The combination of these three inequalities gives dim(G) ≤ Z(G) + 1.

All these results together with Theorem 1 permits to prove a weakening of Conjecture 5 which we restate here: Theorem 6. For every graph G, we have dim(G) ≤ Z(G) + 6c(G).

Proof. By induction with Lemma 36, there exists a spanning tree T such that Z(T ) ≤ Z(G). By Lemma 9, dim(T ) ≤ Z(T ) and thus, dim(G) ≤ 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 ∈ E is part of at most one cycle of G. 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 \ C. Assume by contradiction that two subgraphs G i and G j with 1 ≤ i < j ≤ k are not disjoint. Then, there exists a path P between the vertices v i and v j in G \ 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

As a corollary, we obtain that cactus graphs satisfy Conjecture 5. It improves a result of [START_REF] Eroh | A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs[END_REF] that ensures that Z(G) ≤ 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.

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) ≤ 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 false for even cycles.

Before proving the main result of this section, we need some technical lemmas. Let k ≥ 1 and let G = (V, E) be a graph containing a unique cycle C of length 2k + 1. For u ∈ C, let T u be the connected component of u in G = (V, E \ 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 ∈ C, if T u is not trivial we denote by u the terminal degree of u in G. Else we let u = 0.

Lemma 40. Let G be an odd unicyclic graph. If there exists u ∈ C such that u ≥ 1 then there exists e ∈ E(C) incident to u such that Z(G -e) ≤ 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 ∈ 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 / ∈ Z. Let P be an internal degree-two path between u and a terminal vertex l of G which exists since u ≥ 1. If there is a vertex x in P ∩ Z, then (Z \ {x}) ∪ {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 ∪ {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 ⊆ V be such that for any u on the cycle, S is not a subset of T u . Then, S resolves C. Proof. Let e ∈ E(C) and S be a metric basis of G -e. We will prove that S is still a resolving set of G. Let us first prove that for every u ∈ C since T u is a rooted tree S ∩ T u = ∅. 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 \ {r} does not contain element of S. The tree T u contains at least two connected components of G -e \ {r}, so S ∩ T u = ∅.

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

1. Assume first that x and y are in the same component T u for some

We can assume that α / ∈ T u . Since e / ∈ 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 ∈ T u . For every w ∈ T u , y) and then α resolves (x, y) in G.

Assume now

x and y are in different components, respectively T u and T v . Then, there exist

We will prove by case distinction the following result.

Theorem 43. Any odd unicyclic graph G satisfies dim(G) ≤ Z(G).

Proof. We make a case analysis on the structure of G.

Case 1: For every u ∈ C, T u is a rooted tree. By Lemma 36, there is an edge e such that Z(G -e) ≤ Z(G). Since the G -e is a tree, Corollary 9 ensures that dim(G -e) ≤ Z(G -e). By Lemma 42, dim(G) ≤ dim(G -e). The combination of these inequalities gives dim(G) ≤ Z(G).

A Proof of Lemma 13

The proof of this lemma in the paper of Eroh et al. [START_REF] Eroh | A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs[END_REF] contains a flaw. We present here a correction of the proof based on the same general ideas.

Lemma 13. Let G = (V, E) be a graph and C be a cycle of Proof. Let S be a metric basis of G -e and S i = S ∩ V i for 1 ≤ i ≤ k. Assume without loss of generality that S 1 = ∅. If S i = ∅ for all i = 1, then (G -e) \ G 1 is a path and S 1 ∪ {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 ) = k 2 , then let α 0 ∈ V (C) \ {u i , u j } and S 0 = {α 0 , α i , α j } where α i ∈ S i and α j ∈ S j . Otherwise, let i = 1 be such that S i = ∅, let α 0 = u k 2 and S 0 = {α 0 , α i , α 1 } where α 1 ∈ S 1 and α i ∈ S i . Then, we prove that S ∪ {α 0 } is a resolving set of G. Let v ∈ G i and w ∈ G j with i = j be two vertices in G. We show that one vertex in S 0 resolves the pair (u, v). For simplicity, rename

2 as in Figure 11. Consider first the case where u v / ∈ {u α , u β , u γ } and u w / ∈ {u α , u β , u γ }. Then, we have the following equalities:

Deleting the terms on the form d(u α , α) and equalizing we get

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

which is a contradiction as d(u α , u β ) = k 2 , 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 α or u β . Assume without loss of generalities that u v = u α and u w = u α . Then d(v, α) ≤ d(v, u v ) + d(u α , α) and as d(w, α) = d(w, u w ) + d(u w , u α ) + d(u α , α), we get:

Consider now the distances to

, and so

We assume u w = u α so d(u w , u α ) ≥ 1 and d(u w , u β ) ≤ k 2 by definition of k. We get a contradiction as d(u w , u β ) ≥ 0. The last case is

and summing the two equalities gives:


domain: sde shs sdv

text:
Coordonnées

SOCIAL-ECOLOGICAL FRAMEWORK Development of a city-port complex in the island setting of the Lesser Antilles

DISRUPTING EVENT

From 2010 onwards, the gathering pace of urban-port dynamics in a perspective of sustainable development of the territory of Guadeloupe.

KEY TOPICS

• Evolution of the city-port socio-ecosystem • Circulation and representation of maritime knowledge • Collective management of biodiversity • Resilience of emblematic ecosystems • Modelling of socio-ecosystems TERRITORY Guadeloupe is an archipelago made up of two main islands separated by a narrow inlet associated with several neighbouring islands, Marie-Galante, the archipelago of Les Saintes and La Désirade. This European Outermost Region (OR) is part of one of the world's biodiversity hotspots with a high rate of endemism, and rich and varied ecosystems (coral reefs, mangroves and seagrass meadows) that are particularly sensitive to anthropogenic pressures. This Caribbean territory, with its incredibly rich culture, history and heritage, is also a major tourist attraction.

SOCIAL-ECOLOGICAL ISSUES

Within an island territory, the evolution of port infrastructures and their functions opens avenues for reflection on city-port interactions and the relationship between highly differentiated anthropized spaces. The OHM seeks to analyse the ways in which biodiversity is integrated into the urban-port system, the maintenance or transformation of local knowledge and practices and the dynamics generated by the requalification of Guadeloupe's territories and the evolution of their uses. The reconfiguration of coastal practices and activities and the management of space are central issues. The perception of changes in the seaboard and the involvement of local populations are also two huge social issues for OHM. Moreover, the OHM aims to observe and analyse, in the long term, landscape transformations, the challenges of socio-economic innovations and the changes in relationships between stakeholders and users of the coast.

  ÉCOLOGIQUE (OU « FAIT STRUCTURANT ») Développement d'un complexe urbano-portuaire dans le contexte insulaire des Petites Antilles. ÉVÉNEMENT FONDATEUR A partir des années 2010, accélération des dynamiques urbanoportuaires dans une perspective de développement durable du territoire Guadeloupéen. THÉMATIQUES CLÉS • Evolution du socio-écosystème ville-port • Circulation et représentation des savoirs maritimes • Gestion collective de la biodiversité • Résilience d'écosystèmes emblématiques • Modélisation des socio-écosystèmes TERRITOIRE La Guadeloupe est un archipel constitué de deux îles principales séparées par un étroit bras de mer associé à plusieurs terres voisines, Marie-Galante, l'archipel des Saintes et La Désirade. Cette Région Ultrapériphérique Européenne (RUP) fait partie de l'un des « hotspots » mondiaux de la biodiversité avec un taux d'endémisme important, et des écosystèmes riches et variés (récifs coralliens, mangroves et herbiers) qui sont particulièrement sensibles aux pressions anthropiques. Ce territoire antillais qui présente une exceptionnelle richesse culturelle, historique et patrimoniale est aussi un haut lieu touristique. PROBLÉMATIQUE SOCIO-ÉCOLOGIQUE Au sein d'un territoire insulaire, l'évolution des infrastructures portuaires et de leurs fonctions ouvre des réflexions sur les interactions villeport et sur la mise en relation entre des espaces à anthropisation très différenciées. L'OHM cherche à analyser les manières dont la biodiversité est intégrée au système urbano-portuaire, à la permanence ou aux transformations des pratiques et savoirs locaux, aux dynamiques engendrées par la requalification des territoires guadeloupéens et à l'évolution de leurs usages. La recomposition des pratiques et activités littorales et la gestion des espaces sont des questions centrales. La perception des modifications de la façade maritime et l'implication des populations locales sont également un enjeu primordial. L'OHM vise aussi à observer et à analyser sur le long terme les transformations paysagères, les enjeux d'innovations socio-économiques et l'évolution des rapports entre acteurs et utilisateurs du littoral. 43 rue cuvier, 75005, Paris, France Campus de Fouillole, 97159 Pointe-à-Pitre, Guadeloupe https://ohm-littoral-caraïbe.in2p3.fr/

Guadeloupe, France © Lopez Pascal-Jean © Lopez Pascal-Jean