# Distance-Based Covering Problems for Graphs of Given Cyclomatic Number

Dibyayan Chakraborty, Florent Foucaud, Anni Hakanen

► To cite this version:

Dibyayan Chakraborty, Florent Foucaud, Anni Hakanen. Distance-Based Covering Problems for Graphs of Given Cyclomatic Number. 24th International Symposium on Fundamentals of Computation Theory (FCT 2023), Sep 2023, Trier, Germany. pp.132-146, 10.1007/978-3-031-43587-4_10 . hal-04214541

HAL Id: hal-04214541

https://hal.science/hal-04214541

Submitted on 8 Mar 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Distance-Based Covering Problems for Graphs of Given Cyclomatic Number

Dibyayan Chakraborty, Florent Foucaud, Anni Hakanen

► To cite this version:

Dibyayan Chakraborty, Florent Foucaud, Anni Hakanen. Distance-Based Covering Problems for Graphs of Given Cyclomatic Number. 24th International Symposium on Fundamentals of Computation Theory (FCT 2023), Sep 2023, Trier, Germany. pp.132-146, 10.1007/978-3-031-43587-4_10 . hal-04214541

HAL Id: hal-04214541

https://hal.science/hal-04214541v1

Submitted on 8 Mar 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Distance-based covering problems for graphs of given cyclomatic number*

Dibyayan Chakraborty¹[0000-0003-0534-6417], Florent Foucaud²[0000-0001-8198-693X], and Anni Hakanen²,³[0000-0001-7473-2456]**

¹ Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France

² Université Clermont Auvergne, CNRS, Clermont Auvergne INP, Mines Saint-Étienne, LIMOS, 63000 Clermont-Ferrand, France.

³ Department of Mathematics and Statistics, University of Turku, FI-20014, Finland

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

# 1 Introduction

Distance-based covering problems in graphs are a central class of problems in graphs, both from a structural and from an algorithmic point of view, with

<footnote>* Research funded by the French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25) and by the ANR project GRALMECO (ANR-21-CE48-0004).</footnote>

<footnote>** Corresponding author: anehak@utu.fi. Research supported by the Jenny and Antti Wihuri Foundation and partially by Academy of Finland grant number 338797.</footnote>
# Distance-based covering problems for graphs of given cyclomatic number*

Dibyayan Chakraborty¹[0000-0003-0534-6417], Florent Foucaud²[0000-0001-8198-693X], and Anni Hakanen²,³[0000-0001-7473-2456]**

¹ Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France

² Université Clermont Auvergne, CNRS, Clermont Auvergne INP, Mines Saint-Étienne, LIMOS, 63000 Clermont-Ferrand, France.

³ Department of Mathematics and Statistics, University of Turku, FI-20014, Finland

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

# 1 Introduction

Distance-based covering problems in graphs are a central class of problems in graphs, both from a structural and from an algorithmic point of view, with

<footnote>* Research funded by the French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25) and by the ANR project GRALMECO (ANR-21-CE48-0004).</footnote>

<footnote>** Corresponding author: anehak@utu.fi. Research supported by the Jenny and Antti Wihuri Foundation and partially by Academy of Finland grant number 338797.</footnote>
numerous applications. Our aim is to study such problems for graphs of bounded
cyclomatic number. The latter is a measure of sparsity of the graph that is
popular in both structural and algorithmic graph theory. We will mainly focus
on three types of such problems, as follows.

*Metric dimension and its variants.* In these concepts, introduced in the 1970s [33,16], the aim is to distinguish elements in a graph by using distances. A set $S \subseteq V(G)$ is a *resolving set* of $G$ if for all distinct vertices $x, y \in V(G)$ there exists $s \in S$ such that $d(s, x) \neq d(s, y)$. The smallest possible size of a resolving set of $G$ is called the *metric dimension* of $G$ (denoted by $\dim(G)$). During the last two decades, many variants of resolving sets and metric dimension have been introduced. In addition to the original metric dimension, we consider the edge and mixed metric dimensions of graphs. A set $S \subseteq V(G)$ is an *edge resolving set* of $G$ if for all distinct edges $x, y \in E(G)$ there exists $s \in S$ such that $d(s, x) \neq d(s, y)$, where the distance from a vertex $v$ to an edge $e = e_1e_2$ is defined as $\min\{d(v, e_1), d(v, e_2)\}$ [18]. A mixed resolving set is both a resolving set and an edge resolving set, but it must also distinguish vertices from edges and vice versa; a set $S \subseteq V(G)$ is a *mixed resolving set* of $G$ if for all distinct $x, y \in V(G) \cup E(G)$ there exists $s \in S$ such that $d(s, x) \neq d(s, y)$ [17]. The *edge metric dimension* $\mathrm{edim}(G)$ (resp. *mixed metric dimension* $\mathrm{mdim}(G)$) is the smallest size of an edge resolving set (resp. mixed resolving set) of $G$. More on the different variants of metric dimension and their applications (such as detection problems in networks, graph isomorphism, coin-weighing problems or machine learning) can be found in the recent surveys [22,34].

*Geodetic numbers.* A *geodetic set* of a graph *G* is a set *S* of vertices such that any vertex of *G* lies on some shortest path between two vertices of *S* [15]. The *geodetic number* of *G* is the smallest possible size of a geodetic set of *G*. The version where the edges must be covered is called an *edge-geodetic set* [3]. “Strong” versions of these notions have been studied. A *strong (edge-) geodetic set* of graph *G* is a set *S* of vertices of *G* such that we can assign for any pair *x*, *y* of vertices of *S* a shortest *xy*-path such that each vertex (edge) of *G* lies on one of the chosen paths [2,24]. Recently, the concept of *monitoring edge-geodetic set* was introduced in [14] as a strengthening of a strong edge-geodetic set: here, for every edge *e*, there must exist two solution vertices *x*, *y* such that *e* lies on *all* shortest paths between *x* and *y*. These concepts have numerous applications related to the field of convexity in graphs, see the book [27].

We also consider the concept of *distance-edge-monitoring-sets* introduced in [12,13], which can be seen as a relaxation of monitoring edge-geodetic sets. A set *S* is a distance-edge-monitoring-set if, for every edge *e* of *G*, there is a vertex *x* of *S* and a vertex *y* of *G* such that *e* lies on all shortest paths between *x* and *y*. The minimum size of such a set is denoted dem(*G*).

*Path covering problems.* In this type of problem, one wishes to cover the vertices (or edges) of a graph using a small number of paths. A *path cover* is a set of paths of a graph *G* such that every vertex of *G* belongs to one of the paths. If one path
numerous applications. Our aim is to study such problems for graphs of bounded
cyclomatic number. The latter is a measure of sparsity of the graph that is
popular in both structural and algorithmic graph theory. We will mainly focus
on three types of such problems, as follows.

*Metric dimension and its variants.* In these concepts, introduced in the 1970s [33,16], the aim is to distinguish elements in a graph by using distances. A set $S \subseteq V(G)$ is a *resolving set* of $G$ if for all distinct vertices $x, y \in V(G)$ there exists $s \in S$ such that $d(s, x) \neq d(s, y)$. The smallest possible size of a resolving set of $G$ is called the *metric dimension* of $G$ (denoted by $\dim(G)$). During the last two decades, many variants of resolving sets and metric dimension have been introduced. In addition to the original metric dimension, we consider the edge and mixed metric dimensions of graphs. A set $S \subseteq V(G)$ is an *edge resolving set* of $G$ if for all distinct edges $x, y \in E(G)$ there exists $s \in S$ such that $d(s, x) \neq d(s, y)$, where the distance from a vertex $v$ to an edge $e = e_1e_2$ is defined as $\min\{d(v, e_1), d(v, e_2)\}$ [18]. A mixed resolving set is both a resolving set and an edge resolving set, but it must also distinguish vertices from edges and vice versa; a set $S \subseteq V(G)$ is a *mixed resolving set* of $G$ if for all distinct $x, y \in V(G) \cup E(G)$ there exists $s \in S$ such that $d(s, x) \neq d(s, y)$ [17]. The *edge metric dimension* $\mathrm{edim}(G)$ (resp. *mixed metric dimension* $\mathrm{mdim}(G)$) is the smallest size of an edge resolving set (resp. mixed resolving set) of $G$. More on the different variants of metric dimension and their applications (such as detection problems in networks, graph isomorphism, coin-weighing problems or machine learning) can be found in the recent surveys [22,34].

*Geodetic numbers.* A *geodetic set* of a graph *G* is a set *S* of vertices such that any vertex of *G* lies on some shortest path between two vertices of *S* [15]. The *geodetic number* of *G* is the smallest possible size of a geodetic set of *G*. The version where the edges must be covered is called an *edge-geodetic set* [3]. “Strong” versions of these notions have been studied. A *strong (edge-) geodetic set* of graph *G* is a set *S* of vertices of *G* such that we can assign for any pair *x*, *y* of vertices of *S* a shortest *xy*-path such that each vertex (edge) of *G* lies on one of the chosen paths [2,24]. Recently, the concept of *monitoring edge-geodetic set* was introduced in [14] as a strengthening of a strong edge-geodetic set: here, for every edge *e*, there must exist two solution vertices *x*, *y* such that *e* lies on *all* shortest paths between *x* and *y*. These concepts have numerous applications related to the field of convexity in graphs, see the book [27].

We also consider the concept of *distance-edge-monitoring-sets* introduced in [12,13], which can be seen as a relaxation of monitoring edge-geodetic sets. A set *S* is a distance-edge-monitoring-set if, for every edge *e* of *G*, there is a vertex *x* of *S* and a vertex *y* of *G* such that *e* lies on all shortest paths between *x* and *y*. The minimum size of such a set is denoted dem(*G*).

*Path covering problems.* In this type of problem, one wishes to cover the vertices (or edges) of a graph using a small number of paths. A *path cover* is a set of paths of a graph *G* such that every vertex of *G* belongs to one of the paths. If one path
suffices, the graph is said to be Hamiltonian, and deciding this property is one of the most fundamental algorithmic complexity problems. The paths may be required to be shortest paths, in which case we have the notion of an *isometric path cover* [11,5]; if they are required to be chordless, we have an *induced path cover* [25]. The edge-covering versions have also been studied [1]. This type of problems has numerous applications, such as program and circuit testing [1,26], or bioinformatics [4].

*Our goal.* Our objective is to study the three above classes of problems, on graphs of bounded cyclomatic number. (See Figure 1 for a diagram showing the relationships between the optimal solution sizes of the studied problems.) A *feedback edge set* of a graph *G* is a set of edges whose removal turns *G* into a forest. The smallest size of such a set, denoted by *c*(*G*), is the *cyclomatic number* of *G*. It is sometimes called the *feedback edge (set) number* or the *cycle rank* of *G*. For a graph *G* on *n* vertices, *m* edges and *k* connected components, it is not difficult to see that we have *c*(*G*) = *m* − *n* + *k*, since a forest on *n* vertices with *k* components has *n* − *k* edges. In this paper, we assume all our graphs to be connected. To find an optimal feedback edge set of a connected graph, it suffices to consider a spanning tree; the edges not belonging to the spanning tree form a minimum-size feedback edge set.

Graphs whose cyclomatic number is constant have a relatively simple structure. They are sparse (in the sense that they have a linear number of edges). They also have bounded treewidth (indeed the treewidth is at most the cyclomatic number), a parameter that plays a central role in the area of graph algorithms, see for example Courcelle's celebrated theorem [8]. Thus, they are studied extensively from the perspective of algorithms (for example for the metric dimension [10], the geodetic number [19] or other graph problems [7,35]). They are also studied from a more structural angle [30,31,32].

*Conjectures addressed in this paper.* In order to formally present the conjectures, we need to introduce some structural concepts and notations. A *leaf* of a graph *G* is a vertex of degree 1, and the number of leaves of *G* is denoted by $\ell(G)$. Consider a vertex $v \in V(G)$ of degree at least 3. A *leg* attached to the vertex $v$ is a path $p_1 \dots p_k$ such that $p_1$ is adjacent to $v$, $\deg_G(p_k) = 1$ and $\deg_G(p_i) = 2$ for all $i \neq k$. The number of legs attached to the vertex $v$ is denoted by $l(v)$.

A set $R \subseteq V(G)$ is a *branch-resolving set* of $G$, if for every vertex $v \in V(G)$ of degree at least 3 the set $R$ contains at least one element from at least $l(v) - 1$ legs attached to $v$. The minimum cardinality of a branch-resolving set of $G$ is denoted by $L(G)$, and we have

$$L(G) = \sum_{v \in V(G), \deg(v) \ge 3, l(v) > 1} (l(v) - 1).$$

It is well-known that for any tree $T$ with at least one vertex of degree 3, we have $\dim(T) = L(T)$ (and if $T$ is a path, then $\dim(T) = 1$) [6,16,20,33]. This has motivated the following conjecture.
suffices, the graph is said to be Hamiltonian, and deciding this property is one of the most fundamental algorithmic complexity problems. The paths may be required to be shortest paths, in which case we have the notion of an *isometric path cover* [11,5]; if they are required to be chordless, we have an *induced path cover* [25]. The edge-covering versions have also been studied [1]. This type of problems has numerous applications, such as program and circuit testing [1,26], or bioinformatics [4].

*Our goal.* Our objective is to study the three above classes of problems, on graphs of bounded cyclomatic number. (See Figure 1 for a diagram showing the relationships between the optimal solution sizes of the studied problems.) A *feedback edge set* of a graph *G* is a set of edges whose removal turns *G* into a forest. The smallest size of such a set, denoted by *c*(*G*), is the *cyclomatic number* of *G*. It is sometimes called the *feedback edge (set) number* or the *cycle rank* of *G*. For a graph *G* on *n* vertices, *m* edges and *k* connected components, it is not difficult to see that we have *c*(*G*) = *m* − *n* + *k*, since a forest on *n* vertices with *k* components has *n* − *k* edges. In this paper, we assume all our graphs to be connected. To find an optimal feedback edge set of a connected graph, it suffices to consider a spanning tree; the edges not belonging to the spanning tree form a minimum-size feedback edge set.

Graphs whose cyclomatic number is constant have a relatively simple structure. They are sparse (in the sense that they have a linear number of edges). They also have bounded treewidth (indeed the treewidth is at most the cyclomatic number), a parameter that plays a central role in the area of graph algorithms, see for example Courcelle's celebrated theorem [8]. Thus, they are studied extensively from the perspective of algorithms (for example for the metric dimension [10], the geodetic number [19] or other graph problems [7,35]). They are also studied from a more structural angle [30,31,32].

*Conjectures addressed in this paper.* In order to formally present the conjectures, we need to introduce some structural concepts and notations. A *leaf* of a graph *G* is a vertex of degree 1, and the number of leaves of *G* is denoted by $\ell(G)$. Consider a vertex $v \in V(G)$ of degree at least 3. A *leg* attached to the vertex $v$ is a path $p_1 \dots p_k$ such that $p_1$ is adjacent to $v$, $\deg_G(p_k) = 1$ and $\deg_G(p_i) = 2$ for all $i \neq k$. The number of legs attached to the vertex $v$ is denoted by $l(v)$.

A set $R \subseteq V(G)$ is a *branch-resolving set* of $G$, if for every vertex $v \in V(G)$ of degree at least 3 the set $R$ contains at least one element from at least $l(v) - 1$ legs attached to $v$. The minimum cardinality of a branch-resolving set of $G$ is denoted by $L(G)$, and we have

$$L(G) = \sum_{v \in V(G), \deg(v) \ge 3, l(v) > 1} (l(v) - 1).$$

It is well-known that for any tree $T$ with at least one vertex of degree 3, we have $\dim(T) = L(T)$ (and if $T$ is a path, then $\dim(T) = 1$) [6,16,20,33]. This has motivated the following conjecture.
**Conjecture 1 ([32]).** Let $G$ be a connected graph with $c(G) \ge 2$. Then $\dim(G) \le L(G) + 2c(G)$ and $\mathrm{edim}(G) \le L(G) + 2c(G)$.

The restriction $c(G) \ge 2$ is missing from the original formulation of Conjecture 1 in [32]. However, Sedlar and Škrekovski have communicated to us that this restriction should be included in the conjecture. Conjecture 1 holds for cacti with $c(G) \ge 2$ [32]. The bound $\dim(G) \le L(G) + 18c(G) - 18$ was shown in [10] (for $c(G) \ge 2$), and is the first bound established for the metric dimension in terms of $L(G)$ and $c(G)$.

**Conjecture 2 ([31]).** If $\delta(G) \ge 2$ and $G \ne C_n$, then $\dim(G) \le 2c(G) - 1$ and $\mathrm{edim}(G) \le 2c(G) - 1$.

In [31], Sedlar and Škrekovski showed that Conjecture 2 holds for graphs with minimum degree at least 3. They also showed that if Conjecture 2 holds for all 2-connected graphs, then it holds for all graphs $G$ with $\delta(G) \ge 2$. Recently, Lu at al. [23] addressed Conjecture 2 and showed that $\dim(G) \le 2c(G) + 1$ when $G$ has minimum degree at least 2.

**Conjecture 3 ([30]).** Let $G$ be a connected graph. If $G \ne C_n$, then $\mathrm{mdim}(G) \le l(G) + 2c(G)$.

Conjecture 3 is known to hold for trees [17], cacti and 3-connected graphs [30], and balanced theta graphs [29].

The following conjecture was also posed recently.

**Conjecture 4 ([12,13]).** For any graph $G$, $\dim(G) \le c(G) + 1$.

The original authors of the conjecture proved the bound when $c(G) \le 2$, and proved that the bound $\dim(G) \le 2c(G) - 2$ holds when $c(G) \ge 3$ [12]. The conjectured bound would be tight [12,13].

*Our contributions.* In this paper, we are motivated by Conjectures 1-4, which we address. We will show that both $\dim(G)$ and $\mathrm{edim}(G)$ are bounded from above by $L(G) + 2c(G) + 1$ for all connected graphs $G$. Moreover, we show that if $L(G) \ne 0$, then the bounds of Conjecture 1 hold.

We show that Conjecture 3 is true when $\delta(G) = 1$, and when $\delta(G) \ge 2$ and $G$ contains a cut-vertex. We also show that $\mathrm{mdim}(G) \le 2c(G) + 1$ in all other cases. We also consider the first part of Conjecture 1, that $\dim(G) \le L(G) + 2c(G)$ from [32], in the case where $\delta(G) = 1$, and we show that it is true when $L(G) \ge 1$ and otherwise we have $\dim(G) \le 2c(G) + 1$. We also consider the conjecture that $\mathrm{edim}(G) \le L(G) + 2c(G)$ from [32], and we show that it is true when $\delta(G) = 1$ and $L(G) \ge 1$, and when $\delta(G) \ge 2$ and $G$ contains a cut-vertex. We also show that $\mathrm{edim}(G) \le 2c(G) + 1$ in all other cases.

Thus, our results yield significant improvements towards the Conjectures 1-3, since they are shown to be true in most cases, and are approximated by an additive term of 1 for all graphs. Moreover, we also resolve in the affirmative Conjecture 4.
**Conjecture 1 ([32]).** Let $G$ be a connected graph with $c(G) \ge 2$. Then $\dim(G) \le L(G) + 2c(G)$ and $\mathrm{edim}(G) \le L(G) + 2c(G)$.

The restriction $c(G) \ge 2$ is missing from the original formulation of Conjecture 1 in [32]. However, Sedlar and Škrekovski have communicated to us that this restriction should be included in the conjecture. Conjecture 1 holds for cacti with $c(G) \ge 2$ [32]. The bound $\dim(G) \le L(G) + 18c(G) - 18$ was shown in [10] (for $c(G) \ge 2$), and is the first bound established for the metric dimension in terms of $L(G)$ and $c(G)$.

**Conjecture 2 ([31]).** If $\delta(G) \ge 2$ and $G \ne C_n$, then $\dim(G) \le 2c(G) - 1$ and $\mathrm{edim}(G) \le 2c(G) - 1$.

In [31], Sedlar and Škrekovski showed that Conjecture 2 holds for graphs with minimum degree at least 3. They also showed that if Conjecture 2 holds for all 2-connected graphs, then it holds for all graphs $G$ with $\delta(G) \ge 2$. Recently, Lu at al. [23] addressed Conjecture 2 and showed that $\dim(G) \le 2c(G) + 1$ when $G$ has minimum degree at least 2.

**Conjecture 3 ([30]).** Let $G$ be a connected graph. If $G \ne C_n$, then $\mathrm{mdim}(G) \le l(G) + 2c(G)$.

Conjecture 3 is known to hold for trees [17], cacti and 3-connected graphs [30], and balanced theta graphs [29].

The following conjecture was also posed recently.

**Conjecture 4 ([12,13]).** For any graph $G$, $\dim(G) \le c(G) + 1$.

The original authors of the conjecture proved the bound when $c(G) \le 2$, and proved that the bound $\dim(G) \le 2c(G) - 2$ holds when $c(G) \ge 3$ [12]. The conjectured bound would be tight [12,13].

*Our contributions.* In this paper, we are motivated by Conjectures 1-4, which we address. We will show that both $\dim(G)$ and $\mathrm{edim}(G)$ are bounded from above by $L(G) + 2c(G) + 1$ for all connected graphs $G$. Moreover, we show that if $L(G) \ne 0$, then the bounds of Conjecture 1 hold.

We show that Conjecture 3 is true when $\delta(G) = 1$, and when $\delta(G) \ge 2$ and $G$ contains a cut-vertex. We also show that $\dim(G) \le 2c(G) + 1$ in all other cases. We also consider the first part of Conjecture 1, that $\dim(G) \le L(G) + 2c(G)$ from [32], in the case where $\delta(G) = 1$, and we show that it is true when $L(G) \ge 1$ and otherwise we have $\dim(G) \le 2c(G) + 1$. We also consider the conjecture that $\mathrm{edim}(G) \le L(G) + 2c(G)$ from [32], and we show that it is true when $\delta(G) = 1$ and $L(G) \ge 1$, and when $\delta(G) \ge 2$ and $G$ contains a cut-vertex. We also show that $\mathrm{edim}(G) \le 2c(G) + 1$ in all other cases.

Thus, our results yield significant improvements towards the Conjectures 1-3, since they are shown to be true in most cases, and are approximated by an additive term of 1 for all graphs. Moreover, we also resolve in the affirmative Conjecture 4.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Relations between the parameters discussed in the paper. If a parameter *A* has a directed path to parameter *B*, then for any graph, the value of *A* is upper-bounded by a linear function of the value of *B*.</figcaption></figure>

To obtain the above results, we develop a technique from [23], who introduced it in order to study a strengthening of metric dimension called doubly resolving sets in the context of graphs of minimum degree 2. We notice that the technique can be adapted to work for all graphs and in fact it applies to many types of problems: (variants of) metric dimension, (variants of) geodetic sets, and path-covering problems. For all these problems, the technique yields upper bounds of the form $a \cdot c(G) + f(\ell(G))$, where $\ell(G)$ is the number of leaves of $G$, $f$ is a linear function that depends on the respective problem, and $a$ is a small constant.

The technique is based on a breadth-first-search rooted at a specific vertex, that enables to compute an optimal feedback edge set *F* by considering the edges of the graph that are not part of the breadth-first-search spanning tree. We then select vertices of the edges of *F* (or neighbouring vertices); the way to select these vertices depends on the problem. For the metric dimension and path-covering problems, a pre-processing is done to handle the leaves of the graph (for the geodetic set variants, all leaves must be part of the solution). Our results demonstrate that the techniques used by most previous works to handle graphs of bounded cyclomatic number were not precise enough, and the simple technique we employ is much more effective. We believe that it can be used with success in similar contexts in the future.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Relations between the parameters discussed in the paper. If a parameter *A* has a directed path to parameter *B*, then for any graph, the value of *A* is upper-bounded by a linear function of the value of *B*.</figcaption></figure>

To obtain the above results, we develop a technique from [23], who introduced it in order to study a strengthening of metric dimension called doubly resolving sets in the context of graphs of minimum degree 2. We notice that the technique can be adapted to work for all graphs and in fact it applies to many types of problems: (variants of) metric dimension, (variants of) geodetic sets, and path-covering problems. For all these problems, the technique yields upper bounds of the form $a \cdot c(G) + f(\ell(G))$, where $\ell(G)$ is the number of leaves of $G$, $f$ is a linear function that depends on the respective problem, and $a$ is a small constant.

The technique is based on a breadth-first-search rooted at a specific vertex, that enables to compute an optimal feedback edge set *F* by considering the edges of the graph that are not part of the breadth-first-search spanning tree. We then select vertices of the edges of *F* (or neighbouring vertices); the way to select these vertices depends on the problem. For the metric dimension and path-covering problems, a pre-processing is done to handle the leaves of the graph (for the geodetic set variants, all leaves must be part of the solution). Our results demonstrate that the techniques used by most previous works to handle graphs of bounded cyclomatic number were not precise enough, and the simple technique we employ is much more effective. We believe that it can be used with success in similar contexts in the future.
*Algorithmic applications.* For all the considered problems, our method in fact implies that the optimal solutions can be computed in polynomial time for graphs with bounded cyclomatic number. In other words, we obtain XP algorithms with respect to the cyclomatic number. This was already observed in [10] for the metric dimension (thanks to our improved bounds, we now obtain a better running time, however it should be noted that in [10] the more general weighted version of the problem was considered).

*Organisation.* We first describe the general method to compute the special feedback edge set in Section 2. We then use it in Section 3 for the metric dimension and its variants. We then turn to geodetic sets and its variants in Section 4, and to path-covering problems in Section 5. We describe the algorithmic consequence in Section 6, and conclude in Section 7.

## 2 The general method

The length of a path $P$, denoted by $|P|$, is the number of its vertices minus one. A path is *induced* if there are no graph edges joining non-consecutive vertices. A path is *isometric* if it is a shortest path between its endpoints. For two vertices $u, v$ of a graph $G$, $d(u, v)$ denotes the length of an isometric path between $u$ and $v$. Let $r$ be a vertex of $G$. An edge $e = uv \in E(G)$ is a *horizontal edge* with respect to $r$ if $d(u, r) = d(v, r)$ (otherwise, it is a *vertical edge*). For a vertex $u$ of $G$, let $B_r(u)$ denote the set of edges $uv \in E(G)$ such that $d(u, r) = d(v, r) + 1$. A set $F$ of edges of $G$ is *good with respect to $r$* if $F$ contains all horizontal edges with respect to $r$ and for each $u \neq r$, $|B_r(u) \cap F| = |B_r(u)| - 1$. A set $F$ of edges is simply *good* if $F$ is good with respect to some vertex $r \in V(G)$. For a set $F$ of good edges of a graph $G$, let $T_F$ denote the subgraph of $G$ obtained by removing the edges of $F$ from $G$.

**Lemma 5.** For any connected graph $G$ with $n$ vertices and $m$ edges and a vertex $r \in V(G)$, a good edge set with respect to $r$ can be computed in $O(n+m)$ time.

*Proof.* By doing a Breadth First Search on $G$ from $r$, distances of $r$ from $u$ for all $u \in V(G)$ can be computed in $O(n+m)$ time. Then the horizontal and vertical edges can be computed in $O(m)$ time. Then the sets $B_r(u)$ for all $u \in V(G)$ can be computed in $O(n+m)$ time. Hence the set of good edges with respect to $r$ can be computed in $O(n+m)$ time. $\square$

**Lemma 6.** For a set $F$ of good edges with respect to a vertex $r$ of a connected graph $G$, the subgraph $T_F$ is a tree rooted at $r$. Moreover, every path from $r$ to a leaf of $T_F$ is an isometric path in $G$.

*Proof.* First observe that $T_F$ is connected, as each vertex $u$ has exactly one edge $uv \in E(T_F)$ with $d(u, r) = d(v, r) + 1$. Now assume for contradiction that $T_F$ has a cycle $C$. Let $v \in V(C)$ be a vertex that is furthest from $r$ among all vertices of $C$. Formally, $v$ is a vertex such that $d(r, v) = \max\{d(r, w) : w \in V(C)\}$. Let
*Algorithmic applications.* For all the considered problems, our method in fact implies that the optimal solutions can be computed in polynomial time for graphs with bounded cyclomatic number. In other words, we obtain XP algorithms with respect to the cyclomatic number. This was already observed in [10] for the metric dimension (thanks to our improved bounds, we now obtain a better running time, however it should be noted that in [10] the more general weighted version of the problem was considered).

*Organisation.* We first describe the general method to compute the special feed-back edge set in Section 2. We then use it in Section 3 for the metric dimension and its variants. We then turn to geodetic sets and its variants in Section 4, and to path-covering problems in Section 5. We describe the algorithmic consequence in Section 6, and conclude in Section 7.

## 2 The general method

The length of a path $P$, denoted by $|P|$, is the number of its vertices minus one. A path is *induced* if there are no graph edges joining non-consecutive vertices. A path is *isometric* if it is a shortest path between its endpoints. For two vertices $u, v$ of a graph $G$, $d(u, v)$ denotes the length of an isometric path between $u$ and $v$. Let $r$ be a vertex of $G$. An edge $e = uv \in E(G)$ is a *horizontal edge* with respect to $r$ if $d(u, r) = d(v, r)$ (otherwise, it is a *vertical edge*). For a vertex $u$ of $G$, let $B_r(u)$ denote the set of edges $uv \in E(G)$ such that $d(u, r) = d(v, r) + 1$. A set $F$ of edges of $G$ is *good with respect to $r$* if $F$ contains all horizontal edges with respect to $r$ and for each $u \neq r$, $|B_r(u) \cap F| = |B_r(u)| - 1$. A set $F$ of edges is simply *good* if $F$ is good with respect to some vertex $r \in V(G)$. For a set $F$ of good edges of a graph $G$, let $T_F$ denote the subgraph of $G$ obtained by removing the edges of $F$ from $G$.

**Lemma 5.** For any connected graph $G$ with $n$ vertices and $m$ edges and a vertex $r \in V(G)$, a good edge set with respect to $r$ can be computed in $O(n+m)$ time.

*Proof.* By doing a Breadth First Search on $G$ from $r$, distances of $r$ from $u$ for all $u \in V(G)$ can be computed in $O(n+m)$ time. Then the horizontal and vertical edges can be computed in $O(m)$ time. Then the sets $B_r(u)$ for all $u \in V(G)$ can be computed in $O(n+m)$ time. Hence the set of good edges with respect to $r$ can be computed in $O(n+m)$ time. $\square$

**Lemma 6.** For a set $F$ of good edges with respect to a vertex $r$ of a connected graph $G$, the subgraph $T_F$ is a tree rooted at $r$. Moreover, every path from $r$ to a leaf of $T_F$ is an isometric path in $G$.

*Proof.* First observe that $T_F$ is connected, as each vertex $u$ has exactly one edge $uv \in E(T_F)$ with $d(u, r) = d(v, r) + 1$. Now assume for contradiction that $T_F$ has a cycle $C$. Let $v \in V(C)$ be a vertex that is furthest from $r$ among all vertices of $C$. Formally, $v$ is a vertex such that $d(r, v) = \max\{d(r, w) : w \in V(C)\}$. Let
$E'$ denote the set of edges in $T_F$ incident to $v$. Observe that $|E'|$ is at least two. Hence either $E'$ contains an horizontal edge, or $E' \cap B_r(v)$ contains at least two edges. Either case contradicts that $F$ is a good edge set with respect to $r$. This proves the first part of the observation.

Now consider a path $P$ from $r$ to a leaf $v$ of $T_F$ and write it as $u_1u_2\dots u_k$ where $u_1 = r$ and $u_k = v$. By definition, we have $d(r, u_i) = d(r, u_{i-1}) + 1$ for each $i \in [2, k]$. Hence, $P$ is an isometric path in $G$. $\square$

**Observation 7.** Any set $F$ of good edges of a connected graph $G$ is a feedback edge set of $G$ with minimum cardinality.

*Proof.* Due to Lemma 6 we have that $T_F$ is a tree and therefore $|F| = m - n + 1$ which is same as the cardinality of a feedback edge set of $G$ with minimum cardinality. $\square$

The *base graph* [10] $G_b$ of a graph $G$ is the graph obtained from $G$ by iteratively removing vertices of degree 1 until there remain no such vertices. We use the base graph in some cases where preprocessing the leaves and other tree-like structures is needed.

## 3 Metric dimension and variants

In this section, we consider three metric dimension variants and conjectures regarding them and the cyclomatic number. We shall use the following result.

Distinct vertices $x, y$ are *doubly resolved* by $v, u \in V(G)$ if $d(v, x) - d(v, y) \neq d(u, x) - d(u, y)$. A set $S \subseteq V(G)$ is a *doubly resolving set of G* if every pair of distinct vertices of $G$ are doubly resolved by a pair of vertices in $S$. Lu et al. [23] constructed a doubly resolving set of $G$ with $\delta(G) \ge 2$ by finding a good edge set with respect to a root $r \in V(G)$ using breadth-first search. We state a result obtained by Lu et al. [23] using the terminologies of this paper.

**Theorem 8 ([23]).** Let $G$ be a connected graph such that $\delta(G) \ge 2$ and $r \in V(G)$. Let $S \subseteq V(G)$ consist of $r$ and the endpoints of the edges of a good edge set with respect to $r$.

(i) The set $S$ is a doubly resolving set of $G$.

(ii) If $r$ is a cut-vertex, then the set $S \setminus \{r\}$ is a doubly resolving set of $G$.

(iii) We have $|S| \le 2c(G) + 1$.

A doubly resolving set of $G$ is also a resolving set of $G$, and thus $\dim(G) \le 2c(G) + 1$ when $\delta(G) \ge 2$ due to Theorem 8. Moreover, if $G$ contains a cut-vertex and $\delta(G) \ge 2$, we have $\dim(G) \le 2c(G)$. Therefore, Conjecture 1 holds for the metric dimension of a graph with $\delta(G) \ge 2$ and at least one cut-vertex.

A doubly resolving set is not necessarily an edge resolving set or a mixed resolving set. Thus, more work is required to show that edge and mixed resolving sets can be constructed with good edge sets. A *layer* of $G$ is a set $L_d = \{v \in V(G) \mid d(r, v) = d\}$ where $r$ is the chosen root and $d$ is a fixed distance.
$E'$ denote the set of edges in $T_F$ incident to $v$. Observe that $|E'|$ is at least two. Hence either $E'$ contains an horizontal edge, or $E' \cap B_r(v)$ contains at least two edges. Either case contradicts that $F$ is a good edge set with respect to $r$. This proves the first part of the observation.

Now consider a path $P$ from $r$ to a leaf $v$ of $T_F$ and write it as $u_1u_2\dots u_k$ where $u_1 = r$ and $u_k = v$. By definition, we have $d(r, u_i) = d(r, u_{i-1}) + 1$ for each $i \in [2, k]$. Hence, $P$ is an isometric path in $G$. $\square$

**Observation 7.** Any set $F$ of good edges of a connected graph $G$ is a feedback edge set of $G$ with minimum cardinality.

*Proof.* Due to Lemma 6 we have that $T_F$ is a tree and therefore $|F| = m - n + 1$ which is same as the cardinality of a feedback edge set of $G$ with minimum cardinality. $\square$

The *base graph* [10] $G_b$ of a graph $G$ is the graph obtained from $G$ by iteratively removing vertices of degree 1 until there remain no such vertices. We use the base graph in some cases where preprocessing the leaves and other tree-like structures is needed.

## 3 Metric dimension and variants

In this section, we consider three metric dimension variants and conjectures regarding them and the cyclomatic number. We shall use the following result.

Distinct vertices $x, y$ are *doubly resolved* by $v, u \in V(G)$ if $d(v, x) - d(v, y) \neq d(u, x) - d(u, y)$. A set $S \subseteq V(G)$ is a *doubly resolving set of G* if every pair of distinct vertices of $G$ are doubly resolved by a pair of vertices in $S$. Lu et al. [23] constructed a doubly resolving set of $G$ with $\delta(G) \ge 2$ by finding a good edge set with respect to a root $r \in V(G)$ using breadth-first search. We state a result obtained by Lu et al. [23] using the terminologies of this paper.

**Theorem 8 ([23]).** Let $G$ be a connected graph such that $\delta(G) \ge 2$ and $r \in V(G)$. Let $S \subseteq V(G)$ consist of $r$ and the endpoints of the edges of a good edge set with respect to $r$.

(i) The set $S$ is a doubly resolving set of $G$.

(ii) If $r$ is a cut-vertex, then the set $S \setminus \{r\}$ is a doubly resolving set of $G$.

(iii) We have $|S| \le 2c(G) + 1$.

A doubly resolving set of $G$ is also a resolving set of $G$, and thus $\dim(G) \le 2c(G)+1$ when $\delta(G) \ge 2$ due to Theorem 8. Moreover, if $G$ contains a cut-vertex and $\delta(G) \ge 2$, we have $\dim(G) \le 2c(G)$. Therefore, Conjecture 1 holds for the metric dimension of a graph with $\delta(G) \ge 2$ and at least one cut-vertex.

A doubly resolving set is not necessarily an edge resolving set or a mixed resolving set. Thus, more work is required to show that edge and mixed resolving sets can be constructed with good edge sets. A *layer* of $G$ is a set $L_d = \{v \in V(G) \mid d(r, v) = d\}$ where $r$ is the chosen root and $d$ is a fixed distance.
**Proposition 9.** Let $G$ be a graph with $\delta(G) \ge 2$, and let $r \in V(G)$. If the set $S$ contains $r$ and the endpoints of a good edge set $F$ with respect to $r$, then $S$ is an edge resolving set.

*Proof.* Suppose to the contrary that there exist distinct edges $e = e_1e_2$ and $f = f_1f_2$ that are not resolved by $S$. In particular, we have $d(r,e) = d(r,f)$. Due to this, say, $e_1$ and $f_1$ are in the same layer $L_d$, and $e_2$ and $f_2$ are in $L_d \cup L_{d+1}$. If $e$ is a horizontal edge with respect to $r$, then $e_1, e_2 \in S$ and $e$ and $f$ are resolved. Thus, neither $e$ nor $f$ is a horizontal edge with respect to $r$ and we have $e_2, f_2 \in L_{d+1}$.

If $e_2 = f_2$, then $e, f \in B_r(e_2)$. Thus, we have $e_2 \in S$ and at least one of $e_1$ and $f_1$ is also in $S$. Now $e$ and $f$ are resolved by $e_1$ or $f_1$. Therefore, we have $e_2 \neq f_2$ and $e_2, f_2 \notin S$.

Let $w \in V(G)$ be a leaf in $T_F$ such that $e_2$ lies on a path between $w$ and $r$ in $T_F$. Since $\delta(G) \ge 2$, the vertex $w$ is an endpoint of some edge in $F$, and thus $w \in S$. Since $e$ and $f$ are not resolved by $S$, we have $d(w, f_2) = d(w, e_2) = d' - d - 1$, where $w \in L_{d'}$, due to the path between $w$ and $r$ being isometric (Lemma 6). Let $P_f$ be a shortest path $w - f_2$ in $G$, and assume that $P_f$ is such that it contains an element of $S$ as close to $f_2$ as possible. Denote this element of $S$ by $s$. We have $s \in L_i$ for some $d+1 < i \le d'$ (notice that we may have $s=w$). As the edges $e$ and $f$ are not resolved by $S$, we have $d(s,e) = d(s,f)$, which implies that $d(s, e_2) = d(s, f_2) = i - d - 1$. Let $P'_e$ and $P'_f$ be shortest paths $s - e_2$ and $s - f_2$, respectively. The paths $P'_e$ and $P'_f$ are internally vertex disjoint, since otherwise the vertex after which the paths diverge is an element of $S$ which contradicts the choice of $P_f$ and $s$. Let $v_e$ and $v_f$ be the vertices adjacent to $s$ in $P'_e$ and $P'_f$, respectively. Now, we have $sv_e, sv_f \in B_r(s)$, and thus $v_e \in S$ (otherwise, $v_f \in S$, which contradicts the choice of $P_f$ and $s$). If $d(v_e, e_2) < d(v_e, f_2)$, then $v_e$ resolves $e$ and $f$, a contradiction. Thus, we have $d(v_e, e_2) \ge d(v_e, f_2)$, but now there exists a shortest path $w - f_2$ that contains $v_e$, which is closer to $f_2$ than $s$ is, a contradiction. $\square$

**Proposition 10.** Let $G$ be a graph with $\delta(G) \ge 2$, and let $r \in V(G)$. If the set $S$ contains $r$ and the endpoints of a good edge set $F$ with respect to $r$, then $S$ is a mixed resolving set.

*Proof.* The set $S$ resolves all pairs of distinct vertices by Theorem 8 and all pairs of distinct edges by Proposition 9. Therefore we only need to show that all pairs consisting of a vertex and an edge are resolved.

Suppose to the contrary that $v \in V(G)$ and $e = e_1e_2 \in E(G)$ are not resolved by $S$. In particular, the root $r$ does not resolve $v$ and $e$, and thus $v, e_1 \in L_d$ for some $d \ge 1$. If $e$ is a horizontal edge, then $e_1, e_2 \in S$ and $e$ and $v$ are resolved. Thus, assume that $e_2 \in L_{d+1}$. Let $w \in V(G)$ be a leaf in $T_F$ such that $e_2$ lies on a path between $w$ and $r$ in $T_F$. Since $\delta(G) \ge 2$, the vertex $w$ is an endpoint of some edge in $F$, and thus $w \in S$. We have $d(w, e_2) = d' - d - 1$, where $w \in L_{d'}$. However, now $d(w, v) \ge d' - d > d(w, e_2)$, and $w$ resolves $v$ and $e$, a contradiction. $\square$
**Proposition 9.** Let $G$ be a graph with $\delta(G) \ge 2$, and let $r \in V(G)$. If the set $S$ contains $r$ and the endpoints of a good edge set $F$ with respect to $r$, then $S$ is an edge resolving set.

*Proof.* Suppose to the contrary that there exist distinct edges $e = e_1e_2$ and $f = f_1f_2$ that are not resolved by $S$. In particular, we have $d(r,e) = d(r,f)$. Due to this, say, $e_1$ and $f_1$ are in the same layer $L_d$, and $e_2$ and $f_2$ are in $L_d \cup L_{d+1}$. If $e$ is a horizontal edge with respect to $r$, then $e_1, e_2 \in S$ and $e$ and $f$ are resolved. Thus, neither $e$ nor $f$ is a horizontal edge with respect to $r$ and we have $e_2, f_2 \in L_{d+1}$.

If $e_2 = f_2$, then $e, f \in B_r(e_2)$. Thus, we have $e_2 \in S$ and at least one of $e_1$ and $f_1$ is also in $S$. Now $e$ and $f$ are resolved by $e_1$ or $f_1$. Therefore, we have $e_2 \neq f_2$ and $e_2, f_2 \notin S$.

Let $w \in V(G)$ be a leaf in $T_F$ such that $e_2$ lies on a path between $w$ and $r$ in $T_F$. Since $\delta(G) \ge 2$, the vertex $w$ is an endpoint of some edge in $F$, and thus $w \in S$. Since $e$ and $f$ are not resolved by $S$, we have $d(w, f_2) = d(w, e_2) = d' - d - 1$, where $w \in L_{d'}$, due to the path between $w$ and $r$ being isometric (Lemma 6). Let $P_f$ be a shortest path $w - f_2$ in $G$, and assume that $P_f$ is such that it contains an element of $S$ as close to $f_2$ as possible. Denote this element of $S$ by $s$. We have $s \in L_i$ for some $d+1 < i \le d'$ (notice that we may have $s=w$). As the edges $e$ and $f$ are not resolved by $S$, we have $d(s,e) = d(s,f)$, which implies that $d(s, e_2) = d(s, f_2) = i - d - 1$. Let $P'_e$ and $P'_f$ be shortest paths $s - e_2$ and $s - f_2$, respectively. The paths $P'_e$ and $P'_f$ are internally vertex disjoint, since otherwise the vertex after which the paths diverge is an element of $S$ which contradicts the choice of $P_f$ and $s$. Let $v_e$ and $v_f$ be the vertices adjacent to $s$ in $P'_e$ and $P'_f$, respectively. Now, we have $sv_e, sv_f \in B_r(s)$, and thus $v_e \in S$ (otherwise, $v_f \in S$, which contradicts the choice of $P_f$ and $s$). If $d(v_e, e_2) < d(v_e, f_2)$, then $v_e$ resolves $e$ and $f$, a contradiction. Thus, we have $d(v_e, e_2) \ge d(v_e, f_2)$, but now there exists a shortest path $w - f_2$ that contains $v_e$, which is closer to $f_2$ than $s$ is, a contradiction. $\square$

**Proposition 10.** Let $G$ be a graph with $\delta(G) \ge 2$, and let $r \in V(G)$. If the set $S$ contains $r$ and the endpoints of a good edge set $F$ with respect to $r$, then $S$ is a mixed resolving set.

*Proof.* The set $S$ resolves all pairs of distinct vertices by Theorem 8 and all pairs of distinct edges by Proposition 9. Therefore we only need to show that all pairs consisting of a vertex and an edge are resolved.

Suppose to the contrary that $v \in V(G)$ and $e = e_1e_2 \in E(G)$ are not resolved by $S$. In particular, the root $r$ does not resolve $v$ and $e$, and thus $v, e_1 \in L_d$ for some $d \ge 1$. If $e$ is a horizontal edge, then $e_1, e_2 \in S$ and $e$ and $v$ are resolved. Thus, assume that $e_2 \in L_{d+1}$. Let $w \in V(G)$ be a leaf in $T_F$ such that $e_2$ lies on a path between $w$ and $r$ in $T_F$. Since $\delta(G) \ge 2$, the vertex $w$ is an endpoint of some edge in $F$, and thus $w \in S$. We have $d(w, e_2) = d' - d - 1$, where $w \in L_{d'}$. However, now $d(w, v) \ge d' - d > d(w, e_2)$, and $w$ resolves $v$ and $e$, a contradiction. $\square$
As pointed out in [23], if $R$ is a doubly resolving set that contains a cut-vertex $v$, then the set $R \setminus \{v\}$ is also a doubly resolving set. The following observation states that the same result holds for mixed resolving sets, and with certain constraints to (edge) resolving sets.

**Observation 11.** Let $G$ be a connected graph with a cut-vertex $v$.

(i) Let $R \subseteq V(G)$ be such that there are at least two connected components in $G-v$ containing elements of $R$. If $d(v,x) \neq d(v,y)$ for some $x, y \in V(G) \cup E(G)$, then there exists an element $s \in R$, $s \neq v$, such that $d(s,x) \neq d(s,y)$.

(ii) If $R \subseteq V(G)$ is a mixed resolving set of $G$, then every connected component of $G-v$ contains at least one element of $R$.

(iii) If $R \subseteq V(G)$ is a resolving set or edge resolving set of $G$, then at most one connected component of $G-v$ does not contain any elements of $R$, and that component is isomorphic to $P_n$ for some $n \ge 1$.

The following corollary follows from Propositions 9 and 10, and Observation 11.

**Corollary 12.** Let $G$ be a graph with $\delta(G) \ge 2$.

(i) If $G$ contains a cut-vertex, then $\mathrm{edim}(G) \le 2c(G)$ and $\mathrm{mdim}(G) \le 2c(G)$.

(ii) If $G$ does not contain a cut-vertex, then $\mathrm{edim}(G) \le 2c(G) + 1$ and $\mathrm{mdim}(G) \le 2c(G) + 1$.

We then turn our attention to graphs with $\delta(G) = 1$. We will show that a good edge set can be used to construct a (edge, mixed) resolving set also in this case. Moreover, we show that Conjecture 3 holds, and Conjecture 1 holds when $L(G) \ge 1$. We also show that $\mathrm{dim}(G)$ and $\mathrm{edim}(G)$ are at most $2c(G) + 1$ when $L(G) = 0$. We use the following results on trees in our proof.

**Proposition 13 ([17]).** Let $T$ be a tree, and let $R \subseteq V(T)$ be the set of leaves of $T$. The set $R$ is a mixed metric basis of $T$.

**Proposition 14 ([18,20]).** Let $T$ be a tree that is not a path. If $R \subseteq V(T)$ is a branch-resolving set of $T$, then it is a resolving set and an edge resolving set.

**Theorem 15.** Let $G$ be a connected graph that is not a tree such that $\delta(G) = 1$. Let $r \in V(G_b)$, and let $S \subseteq V(G_b)$ contain $r$ and the endpoints of a good edge set $F \subseteq E(G_b)$ with respect to $r$. If $R$ is a branch resolving set of $G$, then the set $R \cup S$ is a resolving set and an edge resolving set of $G$. If $R$ is the set of leaves of $G$, then the set $R \cup S$ is a mixed resolving set of $G$.

*Proof.* Let $R$ be either a branch-resolving set of $G$ (for the regular and edge resolving sets) or the set of leaves of $G$ (for mixed metric dimension). We will show that the set $R \cup S$ is a (edge, mixed) resolving set of $G$.

The graph $G-E(G_b)$ is a forest (note that some of the trees might be isolated vertices) where each tree contains a unique vertex of $G_b$. Let us denote these trees by $T_v$, where $v \in V(G_b)$.

Consider distinct $x, y \in V(G) \cup E(G)$. We will show that $x$ and $y$ are resolved by $R \cup S$.
As pointed out in [23], if $R$ is a doubly resolving set that contains a cut-vertex $v$, then the set $R \setminus \{v\}$ is also a doubly resolving set. The following observation states that the same result holds for mixed resolving sets, and with certain constraints to (edge) resolving sets.

**Observation 11.** Let $G$ be a connected graph with a cut-vertex $v$.

(i) Let $R \subseteq V(G)$ be such that there are at least two connected components in $G-v$ containing elements of $R$. If $d(v,x) \neq d(v,y)$ for some $x, y \in V(G) \cup E(G)$, then there exists an element $s \in R$, $s \neq v$, such that $d(s,x) \neq d(s,y)$.

(ii) If $R \subseteq V(G)$ is a mixed resolving set of $G$, then every connected component of $G-v$ contains at least one element of $R$.

(iii) If $R \subseteq V(G)$ is a resolving set or edge resolving set of $G$, then at most one connected component of $G-v$ does not contain any elements of $R$, and that component is isomorphic to $P_n$ for some $n \ge 1$.

The following corollary follows from Propositions 9 and 10, and Observation 11.

**Corollary 12.** Let $G$ be a graph with $\delta(G) \ge 2$.

(i) If $G$ contains a cut-vertex, then $\mathrm{edim}(G) \le 2c(G)$ and $\mathrm{mdim}(G) \le 2c(G)$.

(ii) If $G$ does not contain a cut-vertex, then $\mathrm{edim}(G) \le 2c(G) + 1$ and $\mathrm{mdim}(G) \le 2c(G) + 1$.

We then turn our attention to graphs with $\delta(G) = 1$. We will show that a good edge set can be used to construct a (edge, mixed) resolving set also in this case. Moreover, we show that Conjecture 3 holds, and Conjecture 1 holds when $L(G) \ge 1$. We also show that $\mathrm{dim}(G)$ and $\mathrm{edim}(G)$ are at most $2c(G) + 1$ when $L(G) = 0$. We use the following results on trees in our proof.

**Proposition 13 ([17]).** Let $T$ be a tree, and let $R \subseteq V(T)$ be the set of leaves of $T$. The set $R$ is a mixed metric basis of $T$.

**Proposition 14 ([18,20]).** Let $T$ be a tree that is not a path. If $R \subseteq V(T)$ is a branch-resolving set of $T$, then it is a resolving set and an edge resolving set.

**Theorem 15.** Let $G$ be a connected graph that is not a tree such that $\delta(G) = 1$. Let $r \in V(G_b)$, and let $S \subseteq V(G_b)$ contain $r$ and the endpoints of a good edge set $F \subseteq E(G_b)$ with respect to $r$. If $R$ is a branch resolving set of $G$, then the set $R \cup S$ is a resolving set and an edge resolving set of $G$. If $R$ is the set of leaves of $G$, then the set $R \cup S$ is a mixed resolving set of $G$.

*Proof.* Let $R$ be either a branch-resolving set of $G$ (for the regular and edge resolving sets) or the set of leaves of $G$ (for mixed metric dimension). We will show that the set $R \cup S$ is a (edge, mixed) resolving set of $G$.

The graph $G-E(G_b)$ is a forest (note that some of the trees might be isolated vertices) where each tree contains a unique vertex of $G_b$. Let us denote these trees by $T_v$, where $v \in V(G_b)$.

Consider distinct $x, y \in V(G) \cup E(G)$. We will show that $x$ and $y$ are resolved by $R \cup S$.
- Assume that $x, y \in V(T_v) \cup E(T_v)$ for some $v \in V(G_b)$. Denote $R_v = (V(T_v) \cap R) \cup \{v\}$. The set $R_v$ is a (edge, mixed) resolving set of $T_v$ by Propositions 14 and 13. If $x$ and $y$ are resolved by some element in $R_v$ that is not $v$, then we are done. If $x$ and $y$ are resolved by $v$, then they are resolved by any element in $S \setminus \{v\}$. Since $G$ is not a tree, the set $S \setminus \{v\}$ is clearly nonempty, and $x$ and $y$ are resolved in $G$.

- Assume that $x, y \in V(G_b) \cup E(G_b)$. Now $x$ and $y$ are resolved by $S$ due to Theorem 8, Proposition 9 or Proposition 10.

- Assume that $x \in V(T_v) \cup E(T_v)$ and $y \in V(T_w) \cup E(T_w)$ where $v, w \in V(G_b)$, $v \neq w$. The set $S$ is a doubly resolving set of $G_b$ according to Theorem 8. Thus, there exist distinct $s, t \in S$ such that $d(s, v) - d(s, w) \neq d(t, v) - d(t, w)$. Suppose to the contrary that $d(s, x) = d(s, y)$ and $d(t, x) = d(t, y)$. Now we have

$$d(w, y) - d(v, x) = d(s, v) - d(s, w) \neq d(t, v) - d(t, w) = d(w, y) - d(v, x),$$

a contradiction. Thus, $s$ or $t$ resolves $x$ and $y$.

- Assume that $x \in V(T_v) \cup E(T_v)$ for some $v \in V(G_b)$, $v \neq x$, and $y = y_1y_2 \in E(G_b)$. Suppose that $d(r, x) = d(r, y)$. Without loss of generality, we may assume that $d(r, y) = d(r, y_1) = d$. Now $y_1 \in L_d$ and $v \in L_{d-d_x}$, where $d_x = d(v, x) \in \{0, \dots, d\}$. If $y_2 \in L_d$, then $y$ is a horizontal edge and $y_1, y_2 \in S$. Now $x$ and $y$ are resolved by $y_1$ or $y_2$. So assume that $y_2 \in L_{d+1}$. Let $z \in V(G_b)$ be a leaf in $T_F$ such that $y_2$ lies on a path from $r$ to $z$ in $T_F$. Since $\delta(G_b) \ge 2$, the vertex $z$ is an endpoint of some edge in $F$, and thus $z \in S$. Now $z \in L_{d'}$ for some $d' > d+1$ and $d(z, y_2) = d' - d - 1$ by Lemma 6. Consequently,

$$d(z, x) = d(z, v) + d_x \ge d' - (d - d_x) + d_x = 2d_x + 1 + d(z, y_2) > d(z, y).$$

□

Since the root $r$ can be chosen freely, we can choose the root to be a cut-vertex in $G$ whenever $G$ contains cut-vertices. The bounds in the next corollary then follow from Observations 7 and 11, and Theorem 15.

**Corollary 16.** Let $G$ be a connected graph that is not a tree such that $\delta(G) = 1$. We have $\dim(G) \le \lambda(G) + 2c(G)$, $\mathrm{edim}(G) \le \lambda(G) + 2c(G)$, and $\mathrm{mdim}(G) \le \ell(G) + 2c(G)$, where $\lambda(G) = \max\{L(G), 1\}$.

The relationship of metric dimension and edge metric dimension has garnered a lot of attention since the edge metric dimension was introduced. Zubrilina [36] showed that the ratio $\frac{\dim(G)}{\dim(G)}$ cannot be bounded from above by a constant, and Knor et al. [21] showed the same for the ratio $\frac{\dim(G)}{\mathrm{edim}(G)}$. Inspired by this, Sedlar and Škrekovski [28] conjectured that for a graph $G \neq K_2$, we have $|\dim(G) - \mathrm{edim}(G)| \le c(G)$. This bound, if true, is tight due to the construction presented in [21]. It is easy to see that $\dim(G) \ge \lambda(G)$ and $\mathrm{edim}(G) \ge \lambda(G)$ (the fact that $\dim(G) \ge L(G)$ is shown explicitly in [6], for example). Thus, we now obtain the bound $|\dim(G) - \mathrm{edim}(G)| \le 2c(G)$ due to the bounds established in Corollaries 12 and 16.
- Assume that $x, y \in V(T_v) \cup E(T_v)$ for some $v \in V(G_b)$. Denote $R_v = (V(T_v) \cap R) \cup \{v\}$. The set $R_v$ is a (edge, mixed) resolving set of $T_v$ by Propositions 14 and 13. If $x$ and $y$ are resolved by some element in $R_v$ that is not $v$, then we are done. If $x$ and $y$ are resolved by $v$, then they are resolved by any element in $S \setminus \{v\}$. Since $G$ is not a tree, the set $S \setminus \{v\}$ is clearly nonempty, and $x$ and $y$ are resolved in $G$.

- Assume that $x, y \in V(G_b) \cup E(G_b)$. Now $x$ and $y$ are resolved by $S$ due to Theorem 8, Proposition 9 or Proposition 10.

- Assume that $x \in V(T_v) \cup E(T_v)$ and $y \in V(T_w) \cup E(T_w)$ where $v, w \in V(G_b)$, $v \neq w$. The set $S$ is a doubly resolving set of $G_b$ according to Theorem 8. Thus, there exist distinct $s, t \in S$ such that $d(s, v) - d(s, w) \neq d(t, v) - d(t, w)$. Suppose to the contrary that $d(s, x) = d(s, y)$ and $d(t, x) = d(t, y)$. Now we have

$$d(w, y) - d(v, x) = d(s, v) - d(s, w) \neq d(t, v) - d(t, w) = d(w, y) - d(v, x),$$

a contradiction. Thus, $s$ or $t$ resolves $x$ and $y$.

- Assume that $x \in V(T_v) \cup E(T_v)$ for some $v \in V(G_b)$, $v \neq x$, and $y = y_1y_2 \in E(G_b)$. Suppose that $d(r, x) = d(r, y)$. Without loss of generality, we may assume that $d(r, y) = d(r, y_1) = d$. Now $y_1 \in L_d$ and $v \in L_{d-d_x}$, where $d_x = d(v, x) \in \{0, \dots, d\}$. If $y_2 \in L_d$, then $y$ is a horizontal edge and $y_1, y_2 \in S$. Now $x$ and $y$ are resolved by $y_1$ or $y_2$. So assume that $y_2 \in L_{d+1}$. Let $z \in V(G_b)$ be a leaf in $T_F$ such that $y_2$ lies on a path from $r$ to $z$ in $T_F$. Since $\delta(G_b) \ge 2$, the vertex $z$ is an endpoint of some edge in $F$, and thus $z \in S$. Now $z \in L_{d'}$ for some $d' > d+1$ and $d(z, y_2) = d' - d - 1$ by Lemma 6. Consequently,

$$d(z, x) = d(z, v) + d_x \ge d' - (d - d_x) + d_x = 2d_x + 1 + d(z, y_2) > d(z, y).$$

□

Since the root $r$ can be chosen freely, we can choose the root to be a cut-vertex in $G$ whenever $G$ contains cut-vertices. The bounds in the next corollary then follow from Observations 7 and 11, and Theorem 15.

**Corollary 16.** Let $G$ be a connected graph that is not a tree such that $\delta(G) = 1$. We have $\dim(G) \le \lambda(G) + 2c(G)$, $\mathrm{edim}(G) \le \lambda(G) + 2c(G)$, and $\mathrm{mdim}(G) \le \ell(G) + 2c(G)$, where $\lambda(G) = \max\{L(G), 1\}$.

The relationship of metric dimension and edge metric dimension has garnered a lot of attention since the edge metric dimension was introduced. Zubrilina [36] showed that the ratio $\frac{\dim(G)}{\dim(G)}$ cannot be bounded from above by a constant, and Knor et al. [21] showed the same for the ratio $\frac{\dim(G)}{\mathrm{edim}(G)}$. Inspired by this, Sedlar and Škrekovski [28] conjectured that for a graph $G \neq K_2$, we have $|\dim(G) - \mathrm{edim}(G)| \le c(G)$. This bound, if true, is tight due to the construction presented in [21]. It is easy to see that $\dim(G) \ge \lambda(G)$ and $\mathrm{edim}(G) \ge \lambda(G)$ (the fact that $\dim(G) \ge L(G)$ is shown explicitly in [6], for example). Thus, we now obtain the bound $|\dim(G) - \mathrm{edim}(G)| \le 2c(G)$ due to the bounds established in Corollaries 12 and 16.
# 4 Geodetic sets and variants

We now address the problems related to geodetic sets, and show that the same method can be applied in this context as well. Note that all leaves of a graph belong to any of its geodetic sets. Due to lack of space, we only present the constructions of the solution sets.

## 4.1 Geodetic sets

**Theorem 17 (*)**. Let $G$ be a connected graph. If $G$ has a cut-vertex then $g(G) \le 2c(G) + \ell(G)$. Otherwise, $g(G) \le 2c(G) + 1$.

*Proof (Sketch).* We construct a good set $F$ of edges of $G$ by Lemma 5 (if $G$ has a cut-vertex then the root $r$ shall be a cut-vertex). We select as solution vertices, all leaves of $G$, all endpoints of edges of $F$, and $r$ (only if $G$ is biconnected). $\square$

The upper bound of Theorem 17 is tight when there is a cut-vertex, indeed, consider the graph formed by a disjoint union of $k$ odd cycles and $l$ paths, all identified via a single vertex. This graph has cyclomatic number $k$, $l$ leaves, and geodetic number $2k+l$. When there is no cut-vertex, any odd cycle has geodetic number 3 and cyclomatic number 1, so the bound is tight in this case too.

## 4.2 Monitoring edge-geodetic sets

It was proved in [14] that $\text{meg}(G) \le 9c(G) + \ell(G) - 8$ for every graph $G$, and some graphs were constructed for which $\text{meg}(G) = 3c(G) + \ell(G)$. We next improve the former upper bound, therefore showing that the latter construction is essentially best possible.

**Theorem 18 (*)**. For any graph $G$, we have $\text{meg}(G) \le 3c(G) + \ell(G) + 1$. If $G$ contains a cut-vertex, then $\text{meg}(G) \le 3c(G) + \ell(G)$.

*Proof (Sketch).* We construct a good set $F$ of edges of $G$ by Lemma 5, by choosing $r$ as a vertex belonging to a cycle, if possible. The solution set contains $r$ (if $G$ is biconnected), all leaves of $G$, and for each edge of $F$, both its endpoints. Moreover, for each vertex $u$ of $G$ with $|B_r(u)| \ge 2$, we add all endpoints of the edges of $B_r(u)$. $\square$

## 4.3 Distance-edge-monitoring-sets

We now prove Conjecture 4.

**Theorem 19 (*)**. For any connected graph $G$, $\text{dem}(G) \le c(G) + 1$.

*Proof (Sketch).* We construct a good set $F$ of edges of the base graph $G_b$ of $G$ by Lemma 5, and select as solution vertices the root $r$, one arbitrary endpoint of each horizontal edges of $F$, as well as each vertex $v$ with $|B_r(v)| \ge 2$. $\square$
# 4 Geodetic sets and variants

We now address the problems related to geodetic sets, and show that the same method can be applied in this context as well. Note that all leaves of a graph belong to any of its geodetic sets. Due to lack of space, we only present the constructions of the solution sets.

## 4.1 Geodetic sets

**Theorem 17 (*)**. Let $G$ be a connected graph. If $G$ has a cut-vertex then $g(G) \le 2c(G) + \ell(G)$. Otherwise, $g(G) \le 2c(G) + 1$.

*Proof (Sketch)*. We construct a good set $F$ of edges of $G$ by Lemma 5 (if $G$ has a cut-vertex then the root $r$ shall be a cut-vertex). We select as solution vertices, all leaves of $G$, all endpoints of edges of $F$, and $r$ (only if $G$ is biconnected). $\square$

The upper bound of Theorem 17 is tight when there is a cut-vertex, indeed, consider the graph formed by a disjoint union of $k$ odd cycles and $l$ paths, all identified via a single vertex. This graph has cyclomatic number $k$, $l$ leaves, and geodetic number $2k+l$. When there is no cut-vertex, any odd cycle has geodetic number 3 and cyclomatic number 1, so the bound is tight in this case too.

## 4.2 Monitoring edge-geodetic sets

It was proved in [14] that $\text{meg}(G) \le 9c(G) + \ell(G) - 8$ for every graph $G$, and some graphs were constructed for which $\text{meg}(G) = 3c(G) + \ell(G)$. We next improve the former upper bound, therefore showing that the latter construction is essentially best possible.

**Theorem 18 (*)**. For any graph $G$, we have $\text{meg}(G) \le 3c(G) + \ell(G) + 1$. If $G$ contains a cut-vertex, then $\text{meg}(G) \le 3c(G) + \ell(G)$.

*Proof (Sketch)*. We construct a good set $F$ of edges of $G$ by Lemma 5, by choosing $r$ as a vertex belonging to a cycle, if possible. The solution set contains $r$ (if $G$ is biconnected), all leaves of $G$, and for each edge of $F$, both its endpoints. Moreover, for each vertex $u$ of $G$ with $|B_r(u)| \ge 2$, we add all endpoints of the edges of $B_r(u)$. $\square$

## 4.3 Distance-edge-monitoring-sets

We now prove Conjecture 4.

**Theorem 19 (*)**. For any connected graph $G$, $\text{dem}(G) \le c(G) + 1$.

*Proof (Sketch)*. We construct a good set $F$ of edges of the base graph $G_b$ of $G$ by Lemma 5, and select as solution vertices the root $r$, one arbitrary endpoint of each horizontal edges of $F$, as well as each vertex $v$ with $|B_r(v)| \ge 2$. $\square$
# 5 Path covers and variants

In this section, we consider the path covering problems. We focus on isometric path edge-covers (sets of isometric paths that cover all edges of the graph), indeed those have the most restrictive definition and the bound thus holds for all other path covering problems from Figure 1.

**Theorem 20 (*)**. For any graph $G$, ipec $(G) \le 3c(G) + \lceil (\ell(G) + 1)/2 \rceil$.

*Proof (Sketch).* We construct a good set $F$ of edges of the base graph $G_b$ of $G$ by Lemma 5, and select as solution paths the horizontal edges of $F$; for each vertex $v$ with $|B_r(v)| \ge 2$, we add to $S$, $|B_r(v)|$ shortest paths from $v$ to $r$, each starting with a different edge from $B_r(v)$. This covers the edges of $G_b$. To cover the edges of $G - E(G_b)$, we carefully construct (using an iterative procedure) a pairing of the leaves of $G$ and connect each paired pair by a shortest path. $\square$

The upper bound of Theorem 20 is nearly tight, indeed, consider (again) the graph formed by a disjoint union of $k$ odd cycles and $l$ paths, all identified via a single vertex. The obtained graph has cyclomatic number $k$, $l$ leaves, and isometric path edge-cover number $3k + \lceil l/2 \rceil$.

# 6 Algorithmic consequences

**Theorem 21 (*)**. For all the problems considered here, if we have an upper bound on the solution size of $a \cdot c(G) + f(\ell(G))$ for some $a \in \mathbb{N}$, we obtain an algorithm with running time $O(n^{a \cdot c(G)})$ on graphs $G$ of order $n$.

*Proof (Sketch).* One needs to be able to compute the optimal number of leaves required in a solution, using the methods described in the proofs of the theorems. Then, a simple brute-force algorithm trying all subsets of size $a \cdot c(G)$ completes the algorithm. $\square$

# 7 Conclusion

We have demonstrated that a simple technique based on breadth-first-search is very efficient to obtain bounds for various distance-based covering problems, when the cyclomatic number and the number of leaves are considered. This resolves or advances several open problems and conjectures from the literature on this type of problems. There remain some gaps between the obtained bounds and the conjectures or known constructions, that still need to be closed.

A refinement of the cyclomatic number of a (connected) graph $G$ is called its *max leaf number*, which is the maximum number of leaves in a spanning tree of $G$. It is known that the cyclomatic number is always upper-bounded by the max leaf number plus the number of leaves [9], so, all our bounds also imply bounds using the max leaf number only.
# 5 Path covers and variants

In this section, we consider the path covering problems. We focus on isometric path edge-covers (sets of isometric paths that cover all edges of the graph), indeed those have the most restrictive definition and the bound thus holds for all other path covering problems from Figure 1.

**Theorem 20 (*)**. For any graph $G$, ipec $(G) \le 3c(G) + \lceil (\ell(G) + 1)/2 \rceil$.

*Proof (Sketch).* We construct a good set $F$ of edges of the base graph $G_b$ of $G$ by Lemma 5, and select as solution paths the horizontal edges of $F$; for each vertex $v$ with $|B_r(v)| \ge 2$, we add to $S$, $|B_r(v)|$ shortest paths from $v$ to $r$, each starting with a different edge from $B_r(v)$. This covers the edges of $G_b$. To cover the edges of $G - E(G_b)$, we carefully construct (using an iterative procedure) a pairing of the leaves of $G$ and connect each paired pair by a shortest path. $\square$

The upper bound of Theorem 20 is nearly tight, indeed, consider (again) the graph formed by a disjoint union of $k$ odd cycles and $l$ paths, all identified via a single vertex. The obtained graph has cyclomatic number $k$, $l$ leaves, and isometric path edge-cover number $3k + \lceil l/2 \rceil$.

# 6 Algorithmic consequences

**Theorem 21 (*)**. For all the problems considered here, if we have an upper bound on the solution size of $a \cdot c(G) + f(\ell(G))$ for some $a \in \mathbb{N}$, we obtain an algorithm with running time $O(n^{a \cdot c(G)})$ on graphs $G$ of order $n$.

*Proof (Sketch).* One needs to be able to compute the optimal number of leaves required in a solution, using the methods described in the proofs of the theorems. Then, a simple brute-force algorithm trying all subsets of size $a \cdot c(G)$ completes the algorithm. $\square$

# 7 Conclusion

We have demonstrated that a simple technique based on breadth-first-search is very efficient to obtain bounds for various distance-based covering problems, when the cyclomatic number and the number of leaves are considered. This resolves or advances several open problems and conjectures from the literature on this type of problems. There remain some gaps between the obtained bounds and the conjectures or known constructions, that still need to be closed.

A refinement of the cyclomatic number of a (connected) graph $G$ is called its *max leaf number*, which is the maximum number of leaves in a spanning tree of $G$. It is known that the cyclomatic number is always upper-bounded by the max leaf number plus the number of leaves [9], so, all our bounds also imply bounds using the max leaf number only.
Regarding the algorithmic applications, we note that the XP algorithms described in Theorem 21 can sometimes be improved to obtain an FPT algorithm. This is the case for geodetic sets [19], but whether this is possible for the metric dimension remains a major open problem [9,19] (this is however shown to be possible for the larger parameter "max leaf number" [9]).

## References

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

2. Arokiaraj, A., Klavžar, S., Manuel, P.D., Thomas, E., Xavier, A.: Strong geodetic problems in networks. Discussiones Mathematicae Graph Theory **40**(1), 307–321 (2020)

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

4. Cáceres, M., Cairo, M., Mumey, B., Rizzi, R., Tomescu, A.I.: Sparsifying, shrinking and splicing for minimum path cover in parameterized linear time. In: Proceedings of SODA 2022. pp. 359–376. SIAM (2022)

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

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

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

8. Courcelle, B.: The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Information and Computation **85**(1), 12–75 (1990)

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

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

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

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

13. Foucaud, F., Klasing, R., Miller, M., Ryan, J.: Monitoring the edges of a graph using distances. In: Changat, M., Das, S. (eds.) Proceedings of CALDAM 2020. Lecture Notes in Computer Science, vol. 12016, pp. 28–40 (2020)

14. Foucaud, F., Narayanan, K., Sulochana, L.R.: Monitoring edge-geodetic sets in graphs. In: Bagchi, A., Muthu, R. (eds.) Proceedings of CALDAM 2023. Lecture Notes in Computer Science, vol. 13947, pp. 245–256 (2023)

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

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

17. Kelenc, A., Kuziak, D., Taranenko, A., Yero, I.G.: Mixed metric dimension of graphs. Applied Mathematics and Computation **314**, 429–438 (2017)
Regarding the algorithmic applications, we note that the XP algorithms described in Theorem 21 can sometimes be improved to obtain an FPT algorithm. This is the case for geodetic sets [19], but whether this is possible for the metric dimension remains a major open problem [9,19] (this is however shown to be possible for the larger parameter "max leaf number" [9]).

## References

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

2. Arokiaraj, A., Klavžar, S., Manuel, P.D., Thomas, E., Xavier, A.: Strong geodetic problems in networks. Discussiones Mathematicae Graph Theory **40**(1), 307–321 (2020)

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

4. Cáceres, M., Cairo, M., Mumey, B., Rizzi, R., Tomescu, A.I.: Sparsifying, shrinking and splicing for minimum path cover in parameterized linear time. In: Proceedings of SODA 2022. pp. 359–376. SIAM (2022)

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

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

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

8. Courcelle, B.: The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Information and Computation **85**(1), 12–75 (1990)

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

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

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

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

13. Foucaud, F., Klasing, R., Miller, M., Ryan, J.: Monitoring the edges of a graph using distances. In: Changat, M., Das, S. (eds.) Proceedings of CALDAM 2020. Lecture Notes in Computer Science, vol. 12016, pp. 28–40 (2020)

14. Foucaud, F., Narayanan, K., Sulochana, L.R.: Monitoring edge-geodetic sets in graphs. In: Bagchi, A., Muthu, R. (eds.) Proceedings of CALDAM 2023. Lecture Notes in Computer Science, vol. 13947, pp. 245–256 (2023)

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

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

17. Kelenc, A., Kuziak, D., Taranenko, A., Yero, I.G.: Mixed metric dimension of graphs. Applied Mathematics and Computation **314**, 429–438 (2017)
18. Kelenc, A., Tratnik, N., Yero, I.G.: Uniquely identifying the edges of a graph: The edge metric dimension. Discrete Applied Mathematics 251, 204–220 (2018)

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

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

21. Knor, M., Majstorović, S., Masa Toshi, A.T., Škrekovski, R., Yero, I.G.: Graphs with the edge metric dimension smaller than the metric dimension. Applied Mathematics and Computation 401, 126076 (2021)

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

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

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

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

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

27. Pelayo, I.M.: Geodesic Convexity in Graphs. Springer (2013)

28. Sedlar, J., Škrekovski, R.: Bounds on metric dimensions of graphs with edge disjoint cycles. Applied Mathematics and Computation 396, 125908 (2021)

29. Sedlar, J., Škrekovski, R.: Extremal mixed metric dimension with respect to the cyclomatic number. Applied Mathematics and Computation 404, 126238 (2021)

30. Sedlar, J., Škrekovski, R.: Mixed metric dimension of graphs with edge disjoint cycles. Discrete Applied Mathematics 300, 1–8 (2021)

31. Sedlar, J., Škrekovski, R.: Metric dimensions vs. cyclomatic number of graphs with minimum degree at least two. Applied Mathematics and Computation 427, 127147 (2022)

32. Sedlar, J., Škrekovski, R.: Vertex and edge metric dimensions of cacti. Discrete Applied Mathematics 320, 126–139 (2022)

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

34. Tillquist, R.C., Frongillo, R.M., Lladser, M.E.: Getting the lay of the land in discrete space: A survey of metric dimension and its applications. arXiv preprint arXiv:2104.07201 (2021)

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

36. Zubrilina, N.: On the edge dimension of a graph. Discrete Mathematics 341(7), 2083–2088 (2018)
18. Kelenc, A., Tratnik, N., Yero, I.G.: Uniquely identifying the edges of a graph: The edge metric dimension. Discrete Applied Mathematics 251, 204–220 (2018)

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

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

21. Knor, M., Majstorović, S., Masa Toshi, A.T., Škrekovski, R., Yero, I.G.: Graphs with the edge metric dimension smaller than the metric dimension. Applied Mathematics and Computation 401, 126076 (2021)

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

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

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

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

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

27. Pelayo, I.M.: Geodesic Convexity in Graphs. Springer (2013)

28. Sedlar, J., Škrekovski, R.: Bounds on metric dimensions of graphs with edge disjoint cycles. Applied Mathematics and Computation 396, 125908 (2021)

29. Sedlar, J., Škrekovski, R.: Extremal mixed metric dimension with respect to the cyclomatic number. Applied Mathematics and Computation 404, 126238 (2021)

30. Sedlar, J., Škrekovski, R.: Mixed metric dimension of graphs with edge disjoint cycles. Discrete Applied Mathematics 300, 1–8 (2021)

31. Sedlar, J., Škrekovski, R.: Metric dimensions vs. cyclomatic number of graphs with minimum degree at least two. Applied Mathematics and Computation 427, 127147 (2022)

32. Sedlar, J., Škrekovski, R.: Vertex and edge metric dimensions of cacti. Discrete Applied Mathematics 320, 126–139 (2022)

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

34. Tillquist, R.C., Frongillo, R.M., Lladser, M.E.: Getting the lay of the land in discrete space: A survey of metric dimension and its applications. arXiv preprint arXiv:2104.07201 (2021)

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

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