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

HAL
open science

# Monitoring edge-geodetic sets in graphs: extremal graphs, bounds, complexity

Florent Foucaud, Pierre-Marie Marcille, Zin Mar Myint, R. B. Sandeep, Sagnik Sen, S. Taruni

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

## To cite this version:

Florent Foucaud, Pierre-Marie Marcille, Zin Mar Myint, R. B. Sandeep, Sagnik Sen, et al., Monitoring edge-geodetic sets in graphs: extremal graphs, bounds, complexity. 10th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2024), Feb 2024, Bhilai, India. pp.29-43, 10.1007/978-3-031-52213-0_3. hal-04396469v1

HAL Id: hal-04396469

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

Submitted on 16 Jan 2024 (v1), last revised 3 Dec 2025 (v2)

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.
# Monitoring edge-geodetic sets in graphs: extremal graphs, bounds, complexity

Florent Foucaud<fnref n="1" />, Pierre-Marie Marcille<fnref n="2" />, Zin Mar Myint<fnref n="3" />,*,
R. B. Sandeep<fnref n="3" />, Sagnik Sen<fnref n="3" />, and S Taruni<fnref n="3" />

**Abstract.** A monitoring edge-geodetic set, or simply an MEG-set, of a graph $G$ is a vertex subset $M \subseteq V(G)$ such that given any edge $e$ of $G$, $e$ lies on every shortest $u-v$ path of $G$, for some $u,v \in M$. The monitoring edge-geodetic number of $G$, denoted by $meg(G)$, is the minimum cardinality of such an MEG-set. This notion provides a graph theoretic model of the network monitoring problem.

In this article, we compare $meg(G)$ with some other graph theoretic pa-
rameters stemming from the network monitoring problem and provide
examples of graphs having prescribed values for each of these parameters.
We also characterize graphs $G$ that have $V(G)$ as their minimum MEG-
set, which settles an open problem due to Foucaud et. al. (CALDAM
2023). We also provide a general upper bound for $meg(G)$ for sparse
graphs in terms of their girth, and later refine the upper bound using
the chromatic number of $G$. We examine the change in $meg(G)$ with
respect to two fundamental graph operations: clique-sum and subdivi-
sions. In both cases, we provide a lower and an upper bound of the possi-
ble amount of changes and provide (almost) tight examples. Finally, we
prove that the decision version of the problem of finding $meg(G)$ is NP-
complete even for the family of 3-degenerate, 2 apex graphs, improving
the existing result by Haslegrave (Discrete Applied Mathematics 2023).

**Keywords:** Geodetic set · Monitoring edge geodetic set · *k*-clique sum · Subdivisions · Chromatic number · Girth · Computational complexity.

# 1 Introduction

In the field of network monitoring, the networking components are monitored
for faults and evaluated to maintain and optimize their availability. In order to

<footnote n="1">¹ Université Clermont Auvergne, CNRS, Clermont Auvergne INP,
Mines Saint-Étienne LIMOS, 63000 Clermont-Ferrand, France

florent.foucaud@uca.fr</footnote>

<footnote n="2">² Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800,
F-33400, Talence, France

pierre-marie.marcille@u-bordeaux.fr</footnote>

<footnote n="3">³ Indian Institute of Technology Dharwad, India
{zinmarmyint.zmm86,sen007isi,taruni.sridhar}@gmail.com,
sandeeprb@iitdh.ac.in</footnote>

<footnote>* Corresponding author.</footnote>
detect failures, one of the popular methods for such monitoring processes involves setting up distance probes [2–4, 13]. At any given time, a distance probe can measure the distance to any other probe in the network. If there is any failure in the connection, then the probes should be able to detect it as there would be a change in the distances between the components. Such networks can be modeled by graphs whose vertices represent the components and the edges represent the connections between them. We select a subset of vertices of the graph and call them probes. This concept of probes that can measure distances in graphs has many real-life applications, for example, it is useful in the fundamental task of routing [10, 15], or using path-oriented tools to monitor IP networks [4], or problems concerning network verification [2, 3, 5]. Based on the requirements of the networks, there have been various related parameters that were defined on graphs in order to study the problem and come up with an effective solution. To name a few, we may mention the geodetic number [8, 9, 12, 16], the edge-geodetic number [1, 25], the strong edge-geodetic number [18, 22], the distance-edge monitoring number [13], and the monitoring edge-geodetic number [14, 17]. The focus of this article is on studying the *monitoring edge-geodetic number* of a graph. We deal with simple graphs, unless otherwise stated.

*Note:* We have omitted some proofs due to space constraints.

## 1.1 Preliminaries

Given a graph $G$, a *monitoring edge-geodetic set* of $G$, or simply, an *MEG-set* of a graph $G$ is a vertex subset $M \subseteq V(G)$ that satisfies the following: given any edge $e$ in $G$, there exists $u, v \in M$ such that $e$ lies on all shortest paths between $u$ and $v$. In such a scenario, we say that the vertices $u, v$ monitor the edge $e$. The monitoring edge-geodetic number, denoted by $meg(G)$, is the smallest size of an MEG-set of $G$.

There are some other related parameters whose definitions are relevant in our context. For convenience, we list them below.

- A *geodetic set* of a graph $G$ is a vertex subset $S \subseteq V(G)$ such that every vertex of $G$ lies on some shortest path between two vertices $u, v \in S$. The *geodetic number*, denoted by $g(G)$, is the minimum $|S|$, where $S$ is a geodetic set of $G$. The concept was introduced by Harary et al. in 1993 [16] and received considerable attention since then, both from the structural side [8, 9, 12] and from the algorithmic side [6, 20].

- An *edge-geodetic set* of a graph $G$ is a vertex subset $S \subseteq V(G)$ such that every edge of $G$ lies on some shortest path between two vertices $u, v \in S$. The *edge-geodetic number*, denoted by $eg(G)$, is the minimum $|S|$, where $S$ is an edge-geodetic set of $G$. This was introduced in 2003 by Atici et al. [1] and further studied from the structural angle [25] as well as algorithmic angle [7, 11].

- A *strong edge-geodetic set* of a graph $G$ is a vertex subset $S \subseteq V(G)$ and an assignment of a particular shortest $u-v$ path $P_{uv}$ to each pair of distinct vertices $u, v \in S$ such that every edge of $G$ lies on $P_{uv}$ for some $u, v \in S$. The
strong edge-geodetic number, denoted by $seg(G)$, is the minimum $|S|$, where $S$ is a geodetic set of $G$. This concept was introduced in 2017 by Manuel et al. [22]. See [18] for some structural studies, and [11] for some algorithmic results.

## 1.2 Motivation of our results and organization of the paper

- In Section 2, we explore the relation between the parameters geodetic number, edge-geodetic number, strong edge-geodetic number, and monitoring edge-geodetic number. As one may have noticed, the above-mentioned graph parameters are closely related and have a natural relation of inclusion. In this section, we construct examples of graphs having prescribed values of the above-mentioned parameters.

- In Section 3 we answer an open question posed by Foucaud, Krishna and Ramasubramony Sulochana [14] on characterizing graphs whose minimum MEG-set is the entire vertex set. We provide such a characterization by proving a necessary and sufficient condition of when a vertex $v$ is part of every MEG-set of graph $G$. Additionally, we also prove a sufficient condition of when a vertex is never part of any minimum MEG-set of the graph.

- In Section 4, we provide upper bounds on $meg(G)$, where $G$ is a sparse graph. Our upper bound is a function of the order of $G$, and its girth. A refinement of the upper bound is provided using the chromatic number of $G$.

- In Section 5, we explore the effect of two fundamental graph operations, namely, the clique-sum and the subdivision on $meg(G)$. We show that $meg(G)$ is both lower and upper bounded by functions related to the operations and that the bounds are (almost) tight.

- In Section 6, we answer another open question that was posed in [14] regarding the computational complexity of finding $meg(G)$. The general question was recently settled by Haslegrave [17], and we give an alternative proof. In fact, our result is stronger, as we show that the decision version of the problem of finding $meg(G)$ is NP-complete even for the restricted class of 3-degenerate, 2-apex graphs.

- In Section 7, we share our concluding remarks which also contain suggestions for future works in this direction.

# 2 Relation between network monitoring parameters

From the definitions, notice that any strong edge-geodetic set is also an edge-geodetic set, and any edge-geodetic set is also a geodetic set (if the graph has no isolated vertices). Moreover, every MEG-set $M$ of a graph is indeed a strong edge-geodetic set, as every edge of $G$ is contained in all the shortest paths between some pair of vertices in $M$. Thus, one can observe the following relations [14],

$$g(G) \le eg(G) \le seg(G) \le meg(G).$$
**Example 1.** Notice that, for any complete graph $K_n$ on $n \ge 2$ vertices, the values of all the parameters are equal to $n$. That is, equality holds in all the inequalities of the above chain of inequalities.

On the other hand, Figure 1 gives an example of a graph where all the inequalities of the above chain of inequalities are strict. To be specific, in this particular example, the values of the parameters increase exactly by one in each step. □

<figure><img src="image_3.png" /><figcaption>**Fig. 1.** A graph $G$ with $2 = g(G) < 3 = eg(G) < 4 = seg(G) < 5 = meg(G)$. Note that, a minimum geodetic set of $G$ is $\{v_3, v_5\}$, a minimum edge-geodetic set of $G$ is $\{v_1, v_2, v_4\}$, a minimum strong edge-geodetic set of $G$ is $\{v_1, v_2, v_3, v_4\}$, and a minimum MEG-set of $G$ is $\{v_1, v_2, v_3, v_4, v_5\}$.</figcaption></figure>

It is natural to ask the question, given four positive integers $a, b, c, d$ satisfying $2 \le a \le b \le c \le d$, is there a graph $G_{a,b,c,d}$ such that we have $g(G_{a,b,c,d}) = a$, $eg(G_{a,b,c,d}) = b$, $seg(G_{a,b,c,d}) = c$, and $meg(G_{a,b,c,d}) = d$? We provide a positive answer to this question except for some specific cases. The rest of the section deals with the construction of such graphs.

**Theorem 1.** For any positive integers $4 \le a \le b \le c \le d$ satisfying $d \ne c + 1$, there exists a connected graph $G_{a,b,c,d}$ with $g(G) = a$, $eg(G) = b$, $seg(G) = c$ and $meg(G) = d$.

*Proof.* We begin the proof by describing the construction of $G_{a,b,c,d}$.

*Construction of $G_{a,b,c,d}$:* In the first phase of the construction, we start with a $K_{2,2+b-a}$, where the partite set of size two has the vertices $x_1$ and $y$, and the partite set of size $(2 + b - a)$ has the vertices $z_1, z_2$ and $w_1, w_2, \dots, w_{b-a}$. Moreover, we add some edges in such a way that the set

$$W = \{w_1, w_2, \dots, w_{b-a}\}$$

becomes a clique. We also add the edge $z_2w_1$.

In the second phase of the construction, we add $(c - b + 1)$ parallel edges between the vertices $z_1$ and $z_2$. After that we subdivide (once) each of the above-mentioned parallel edges and name the degree two vertices created due to the
<figure><img src="image_4.png" /><figcaption>Fig. 2. The structure of $G_{a,b,c,d}$.</figcaption></figure>

subdivisions as $v_1, v_2, \dots, v_{c-b+1}$. The set of these vertices created by the subdivisions is given by

$$V = \{v_1, v_2, \dots, v_{c-b+1}\}.$$

In the third phase of the construction, we add $(a-3)$ pendant neighbors $u_1, u_2, \dots, u_{a-3}$ to $y$, and one pendant neighbor $u_{a-2}$ to $z_1$. Moreover, we attach a long path $x_1x_2\cdots x_{r}u_{a-1}$ with the vertex $x_1$, where $u_{a-1}$ is a pendant vertex and $r = 3\lfloor \frac{d-c}{2} \rfloor + 1$. Next we will add a false twin $x'_{3i}$ to the vertices of the form $x_{3i}$ for $i \in \{1, 2, \dots, \lfloor \frac{d-c}{2} \rfloor\}$. Additionally, if $(d-c)$ is odd, then we will add another twin $x''_{3}$ to the vertex $x_3$. For convenience,

$$U = \{u_1, u_2, \dots, u_{a-1}\}$$

will denote the set of all pendants and

$$X = \{x_{3i}, x'_{3i} | i = 1, 2, \dots, \lfloor \frac{d-c}{2} \rfloor\} \cup \{x''_{3}\}.$$

Note that, $x''_{3}$ exists in $X$ if and only if $(d-c)$ is odd. This completes the description of the construction of the graph $G_{a,b,c,d}$ (see Fig. 2 for a pictorial reference).

As $U$ is the set of all pendants, we know that it will be part of any geodetic set, edge-geodetic set, strong edge-geodetic set, and monitoring edge-geodetic set [14]. However, the vertices of $U$ cannot cover the vertices of $V$ using shortest paths between the vertices of $U$. Therefore, we need at least one more vertex to form a geodetic set. As $U \cup \{z_2\}$ is a geodetic set of $G$, we can infer that

$$g(G_{a,b,c,d}) = (a-1) + 1 = a.$$
Next, observe that the vertices of $U$ are not able to cover any edge of the clique $W$ using shortest paths between the vertices of $U$. Moreover, the only way to monitor those edges is by taking $W$ in our edge-geodetic set. Observe that $U \cup W$ is still not an edge-geodetic set as they are not able to cover the edge $z_2w_1$ by any shortest path between the vertices of $U \cup W$. On the other hand, $U \cup W \cup \{z_2\}$ is an edge-geodetic set. Therefore,

$$eg(G_{a,b,c,d}) = (a-1) + 1 + (b-a) = b.$$

We know that the vertices of $U$ is in any strong edge-geodetic set. Moreover, note that, the vertices of $W$ must be in any strong edge-geodetic set to cover the edges of the clique $W$. Now, let us see how we can cover the edges of the $(c-b+1)$ 2-paths between $z_1, z_2$, having the vertices of $V$ as their internal vertex. First of all, if we do not take $z_2$ in our strong edge-geodetic set, we have to take all vertices of $V$. Second of all, if we take $z_2$ in our strong edge-geodetic set, then we have to take either (at least) all but one vertices of $V$, or all but two vertices of $V$ along with $z_1$ in the strong edge-geodetic set. That means, we need to take at least $(c-b+1)$ additional vertices in the strong edge-geodetic set. Moreover, the set $U \cup W \cup V$ is indeed a strong edge-geodetic set. Thus,

$$seg(G_{a,b,c,d}) = (a-1) + (b-a) + (c-b+1) = c.$$

Finally for any MEG-set, we have to take the vertices of $U$ (as they are pendants), the vertices of $W$ (to monitor the edges of the clique $W$), the vertices of $X$ (as they are twins [14]). However, even with these vertices, we cannot monitor the edges of the $(c-b+1)$ 2-paths between $z_1, z_2$, having the vertices of $V$ as their internal vertex. To do so, we have to take all vertices of $V$ in our MEG-set. However, the set $U \cup W \cup V \cup X$ is an MEG-set. Hence,

$$meg(G_{a,b,c,d}) = (a-1) + (b-a) + (c-b+1) + 2\lfloor\frac{d-c}{2}\rfloor + \epsilon = d,$$

where $\epsilon = 0$ (resp., 1) if $(d-c)$ is (even (resp., odd), and $d \neq c+1$. This completes the proof. □

### 3 Conditions for a vertex being in all or no optimal MEG-sets

In their introductory paper on monitoring edge-geodetic sets, Foucaud, Krishna and Ramasubramony Sulochana [14] asked to characterize the graphs $G$ having $meg(G) = |V(G)|$. We provide a definitive answer to their question, and to this end, we give a necessary and sufficient condition for a vertex to be in any MEG-set of a graph.

**Theorem 2.** Let $G$ be a graph. A vertex $v \in V(G)$ is in every MEG-set of $G$ if and only if there exists $u \in N(v)$ such that any induced 2-path $uvx$ is part of a 4-cycle.
*Proof.* For the necessary condition, let us assume that a vertex $v \in V(G)$ is in every MEG-set of $G$. We have to prove that there exists $u \in N(v)$, such that any induced 2-path $uvx$ is part of a 4-cycle. We prove it by contradiction.

Suppose for every $u \in N(v)$, there exists an induced 2-path $uvx$ such that $uvx$ is not part of a 4-cycle. As $uvx$ is an induced 2-path, observe that $u$ and $x$ are not adjacent, also as $uvx$ is not part of a 4-cycle, we get, $d(u, x) = 2$ and the only shortest path between $u$ and $x$ is via $v$. This implies if we take $u$ and $x$ in our MEG-set $S$, then $xv$ and $uv$ are monitored. Hence, all the neighbors of $v$ can monitor all the edges incident to $v$. Therefore, in particular, $V(G) \setminus \{v\}$ is a MEG-set of $G$. This is a contradiction to the fact that $v$ is in every MEG-set of $G$. Thus, the necessary condition for a vertex $v$ to be part of every MEG-set of $G$ is proved according to the statement.

For the sufficient condition, let us assume that for some vertex $v$ of $G$, there exists $u \in N(v)$ such that any induced 2-path $uvx$ is part of a 4-cycle. We need to prove that $v$ is in every MEG-set. Thus, it is enough to show that $S = V(G) \setminus \{v\}$ is not an MEG-set of $G$. Therefore, we would like to find an edge which is not monitored by the vertices of $S$.

We first observe that if there does not exist any induced 2-path of the form $uvx$, then $v$ must be a simplicial vertex, and thus we know that [14] $v$ belongs to every MEG-set of $G$. On the other hand, if there exists an induced 2-path of the form $uvx$, then there are at least two shortest paths between $u$ and $x$. In particular, $u$ and $x$ cannot monitor the edge $uv$. As $x$ is arbitrary, the vertices of $S$ are not able to monitor the edge $uv$ which implies that $v$ has to be part of every MEG-set. This concludes the proof. $\square$

**Corollary 1.** Let $G$ be a graph. $\text{meg}(G) = n$ if and only if for every $v \in V(G)$, there exists $u \in N(v)$ such that any induced 2-path $uvx$ is part of a 4-cycle.

*Proof.* The proof directly follows from Theorem 2. $\square$

Observe that the condition for $\text{meg}(G) = n$ can be verified in polynomial time due to Corollary 1.

**Corollary 2.** If $G \neq K_2$ is a connected graph of order $n$ and girth $g \geq 5$, then $\text{meg}(G) \leq n - 1$.

*Proof.* Notice that, if a vertex $v$ of $G$ satisfies the condition of Theorem 2, then either $v$ has to be part of a 4-cycle, or $v$ has to be simplicial. As $G$ has girth $g \geq 5$, the only way for $v$ to satisfy the condition is by being a pendant vertex. If all vertices of $G$ are pendant vertices, then $G = K_2$, which is not possible. Thus, not every vertex of $G$ can satisfy the condition of Theorem 2. Hence, $\text{meg}(G) \leq n - 1$. $\square$

We also give a sufficient condition for when a vertex is never part of any minimum MEG-set of a graph. This is a useful tool to eliminate such vertices while finding a minimum MEG-set of a given graph.
**Proposition 1.** Let $G$ be a graph with a path $v_0v_1\cdots v_{k-1}v_k$ whose internal vertices have degree two, $v_0$ has degree at least two, and $v_k$ has degree one. Then the vertices $v_0, v_1, \cdots, v_{k-1}$ are never part of any minimum MEG-set.

*Proof.* Firstly, $v_k$ is part of any MEG-set of $G$ as it is a simplicial vertex [14]. Let $P$ be a shortest path with one of its end points being $v_i$, for some $i \in \{0, 1, \cdots, k-1\}$, while the other end point is $w$ (say). Moreover, assume that $v_j$ is not a vertex of the path $P$, for any value of $j \in \{i+1, i+2, \cdots, k-1\}$. Observe that, the path $P'$ obtained by augmenting the path $v_{i+1}v_{i+2}\cdots v_k$ to $P$ is also a shortest path between $w$ and $v_k$. Thus, in a minimum MEG-set of $G$, the inclusion of any of the vertices $v_0, v_1, \cdots, v_{k-1}$ is redundant. $\square$

**Corollary 3.** Let $G \neq K_2$ be connected graph. Let $v$ be a vertex of $G$ having a pendant neighbor $u$. Then $v$ is never part of any minimum MEG-set of $G$.

*Proof.* The proof follows directly from Proposition 1 as a special case where $v = v_0$ and $u = v_k$. $\square$

**Remark 1.** Due to Proposition 1, for a connected graph $G \neq K_2$, every vertex of degree one must be part of any MEG-set, and its neighbor must not be a part of any MEG-set. Therefore, if $\text{meg}(G) = |V(G)|$, then $G$ must have minimum degree at least 2.

# 4 Sparse graphs

Due to Proposition 1, it makes sense to study connected graphs with minimum degree 2 only. In Corollary 2 we noted that $\text{meg}(G)$, if $G$ has girth 5 or more, cannot be equal to the order of $G$. Therefore, it is natural to wonder whether $\text{meg}(G)$ will become even smaller (with respect to the order of $G$) if $G$ becomes sparser. One way to consider sparse graphs is to study graphs having high girth.

**Theorem 3.** Let $G$ be a connected graph having minimum degree at least 2. If $G$ has $n$ vertices and girth $g$, then $\text{meg}(G) \le \frac{4n}{g+1}$.

*Proof.* Let $G$ be a connected graph having minimum degree at least 2, having $n$ vertices, and girth $g$. We construct a vertex subset $M$ of $G$ recursively, and claim that $M$ is an MEG-set of $G$. To begin with, we initialize $M$ by picking an arbitrary vertex of $G$. Next, we add an arbitrary vertex to $M$ that is at a distance at least $\frac{g-3}{4}$ from each vertex of $M$. We repeat this process until every vertex of $V(G) \setminus M$ are at a distance strictly less than $\frac{g-3}{4}$ from some vertex of $M$.

Next, we will show that $M$ is indeed an MEG-set of $G$. Let $uv$ be an arbitrary edge of $G$. Assume without loss of generality that there exists $u' \in M$ such that $d(u, u') \le \frac{g-3}{4}$ and $d(v, u') > d(u, u')$. Denote $v'$ the vertex of $M$ closest to $v$ that is not $u'$. Let $P_1$ be a shortest path connecting $u'$ and $u$, and $P_2$ be a shortest path connecting $v$ and $v'$. Let $P$ be the path obtained by augmenting the path $P_1$, the edge $uv$, and the path $P_2$. Note that the length of $P$ is at most $\frac{g-1}{2}$,
otherwise, there would be a vertex of P at distance more than $\frac{g-3}{4}$ of any vertex of M. Moreover, if there exists any other (vertex disjoint) path $P'$ connecting u and v of length $\frac{g-1}{2}$ or less, then it will contradict the fact that G has girth g. That means, P is a shortest path between u' and v', and u', v' monitors the edge uv. This implies that M is an MEG-set of G.

Now we are left with counting the cardinality of M. As G is a connected graph with minimum degree at least 2, each vertex v of M is part of a cycle. Thus, v has at least $2 \times \frac{g-3}{8} = \frac{g-3}{4}$ vertices at distance at most $\frac{g-3}{8}$. Let us denote the set of these vertices by $S_v$. Observe that the vertices of $S_v$ do not belong to M as they are too close (within a distance of $\frac{g-3}{8}$ to v ∈ M. Furthermore, notice that, for two vertices u, v ∈ M, we must have $S_u \cap S_v = \emptyset$, as u and v are at distance at least $\frac{g-3}{4}$. Therefore, we must have

$$n = |V(G)| \geq |M| + |M| \left(\frac{g-3}{4}\right) \implies |M| \leq \frac{4n}{g+1}.$$

This completes the proof. □

*Remark 2.* As girth can be considered as a measure of the sparseness of a graph, the above result shows that $meg(G)$ has a stricter upper bound as the sparseness (in terms of the girth) of G increases. However, the idea used in the proof is quite general and it may be possible to provide a better bound using the same idea for specific families of graphs having more structural information.

The following theorem proves that $meg(G)$ of a sparse graph G is upper bounded by a function of its chromatic number $\chi(G)$.

**Theorem 4.** Let G be a connected graph with girth at least 5 having minimum degree at least 2. If G has n vertices, and chromatic number $\chi(G)$, then $meg(G) \leq n(\frac{\chi(G)-1}{\chi(G)})$.

Using Theorem 4, we provide a corollary for graphs that have pendant vertices.

**Corollary 4.** Let G be a graph with girth at least 5, and $\ell$ pendant vertices. If G has n vertices, and chromatic number $\chi(G)$, then $meg(G) \leq n(\frac{\chi(G)-1}{\chi(G)} + \frac{\ell}{\chi(G)})$.

# 5 Effects of clique-sum and subdivisions

Let $G_1$ and $G_2$ be two graphs having cliques $C_1$ and $C_2$ of size k, respectively. A k-clique-sum of $G_1$ and $G_2$, denoted by $G_1 \oplus_k G_2$, is a graph obtained by gluing the vertices of $C_1$ to the vertices $C_2$ (each vertex of $C_1$ is glued to exactly one vertex of $C_2$), and then deleting one or more edges of the glued clique.

This particular operation between two graphs is a fundamental operation in graph theory and is an important notion in the context of the illustrious graph structure theorem [19, 23]. We investigate the changes in $meg(G)$ with respect to the clique-sum operation.
**Theorem 5.** Let $G_1 \oplus_k G_2$ be a $k$-clique-sum of the graphs $G_1$ and $G_2$ for some $k \ge 2$. Then we have,

$$ meg(G_1) + meg(G_2) - 2k \le meg(G_1 \oplus_k G_2) \le meg(G_1) + meg(G_2). $$

Moreover, both the lower and the upper bounds are tight.

Let $G$ be a graph. We obtain the graph $S_G^\ell$ by subdividing each edge of $G$ exactly $\ell$ times. The graph operation subdivision is also a fundamental graph operation, integral in the theory of topological minors, which can be used for the specification of a graph. Moreover, subdivision can be considered as the inverse operation to edge contraction, which is another fundamental notion that plays an instrumental role in the famous graph minor theorem [21, 24]. The following result proves a relation between $meg(G)$ and $meg(S_G^\ell)$.

**Theorem 6.** For any graph $G$ and for all $\ell \ge 2$, we have

$$ 1 \le \frac{meg(G)}{meg(S_G^\ell)} \le 2. $$

Moreover, the lower bound is tight, and the upper bound is asymptotically tight.

**Remark 3.** We have observed that $meg(S_G^\ell) = k + 1$ when $G = P_k \square P_2$.

# 6 Computational complexity

It is known that, for a fixed integer $k$, checking whether a graph has an MEG-set of size at most $k$ can be done in polynomial time [17]. In the same paper, it is shown that the decision version of the problem is NP-complete, which settled an open question asked in [14].

**Theorem 7 ([17]).** The decision problem of determining for a graph $G$ and a natural number $k$ whether $meg(G) \le k$ is NP-complete.

In this section, we will improve this result by showing NP-completeness for the restricted family of 3-degenerate, 2-apex graphs. Recall that, a graph is $k$-degenerate if every subgraph of it has a vertex of degree at most $k$ and a graph is $k$-apex if it contains a set of at most $k$ vertices whose removal yields a planar graph.

In Theorem 7, the reduction was from the Boolean satisfiability problem, whereas, in our proof, we reduce from the VERTEX COVER problem (formally defined below). A vertex cover of a graph $G$ is a vertex subset $S \subseteq V(G)$ such that every edge $e$ in $G$ has at least one end point in $S$. We formally state the decision version of the problem of finding the vertex cover of a graph in the following.
## VERTEX COVER

**Instance:** A graph $G$, an integer $k$.

**Question:** Does $G$ have a vertex cover of size at most $k$?

It is well known that the decision version of the problem is NP-complete. This problem remains NP-complete even when restricted to the family of sub-cubic planar graphs with degeneracy 2 [26]. We state this result as a theorem below.

**Theorem 8 ([26]).** The VERTEX COVER problem is NP-complete even for sub-cubic planar graphs having degeneracy 2.

Next, let us formally present the decision version of the problem of finding $meg(G) \le k$ of a graph $G$, where both $G$ and $k$ are given as inputs.

## MEG-SET

**Instance:** A graph $G$, an integer $k$.

**Question:** Does $G$ have $meg(G) \le k$?

We are now ready to state the main result of this section.

**Theorem 9.** The MEG-SET problem is NP-complete even for 3-degenerate, 2-apex graphs.

We prove Theorem 9 by giving a reduction from the VERTEX COVER problem, that is, by constructing a graph $\hat{G}$ and there by proving the equivalence of finding $meg(\hat{G})$ and finding $\tau(G)$, where $\tau(G)$ is the cardinality of a minimum vertex cover of $G$. Note that, in particular, this improves on the result by Haslegrave [17] which was for general graphs.

**Construction of $\hat{G}$:** Given a graph $G$, we describe the construction of a new graph $\hat{G}$ based on the structure of $G$ in the following. For each edge $e = uv \in E(G)$, we add a 5-path $uu'e'v'v$ starting from $u$ and ending at $v$ and add three pendant vertices $u''$, $e''$, $v''$ for each of the intermediate vertices $u'$, $e'$, $v'$ having degree 2, respectively. Now, add a common neighbor $y$ for all these $u'$, $v'$'s in the newly added paths. After that, we add a pendant vertex $y^*$ to the vertex $y$. Finally, we add a universal vertex $x$ to all the (original) vertices of the graph $G$, and add a pendant vertex $x^*$ to $x$. We denote the so-obtained graph by $\hat{G}$. We refer to Figure 3 for a pictorial reference demonstrating how one edge of $G$ transforms in $\hat{G}$.

We now prove some key lemmas that will help us prove Theorem 9.

**Lemma 1.** The new edges of $\hat{G}$, that is, the edges from the set $E(\hat{G}) \setminus E(G)$, are monitored by the set of all pendant vertices of $\hat{G}$.

*Proof.* Let $e = uv$ be an edge of $G$. Then notice that the pendant vertices of the type $u''$ and $v''$ have a unique shortest path of length 4 connecting them, namely, $u''u'e'v'v''$. This path monitors all the edges on this path, that is, edges of the form $u''u'$, $u'e'$, $e'v'$ and $v'v''$.
<figure><img src="image_5.png" /><figcaption>Fig. 3. A demonstration of the construction of $\hat{G}$.</figcaption></figure>

Moreover, between the pendant vertices of the type $u''$ and $x^*$ (resp., $y^*$), there exists a unique shortest path of length 4 (resp., 3), namely, $u''u'uxx^*$ (resp., $u''u'yy^*$), monitoring the edges of the type $u'u, ux$ (resp., $u'y$), and the edge $xx^*$ (resp., $yy^*$).

Finally, observe that the edges of the form $e''e'$ are monitored by the vertices $u'', e''$ via the unique shortest path $u''u'e'e''$ connecting them. $\square$

**Lemma 2.** Let $G$ be a graph with $n$ vertices and $m$ edges. If $\tau(G) \le k$, then $\text{meg}(\hat{G}) \le k + 3m + 2$.

*Proof.* Let $S$ be a vertex cover of $G$ having $k$ vertices. Let $Z$ be the set of all pendants of $\hat{G}$. We want to show that $|Z| = 3m + 2$, and $S \cup Z$ is an MEG-set of $\hat{G}$.

First observe that, for each edge $e = uv$ of $G$, there are three pendant vertices $u''$, $e''$, $v''$. This amounts to $3m$ pendants in $\hat{G}$. Moreover, counting the pendant neighbors $x^*, y^*$ of $x, y$, respectively, we have $3m + 2$ pendant vertices in total, that is, $|Z| = 3m + 2$.

By Lemma 1, the pendant vertices are enough to monitor all the edges of $\hat{G}$, except, maybe, the (original) edges of $G$. Let us suppose that the vertex $u$ is in our MEG-set. An immediate consequence of having $u$ and the set $Z$ of all pendants in an MEG-set is that, between $u$ and the pendant vertex $v''$, there is a unique shortest path $uvv'v''$, which monitors the edge $uv$. That means, a vertex $u$ and the vertices of $Z$, monitors all the edges incident to $v$. Thus, $S \cup Z$ monitors every edge of $\hat{G}$, and hence, $\text{meg}(\hat{G}) \le |S \cup Z| \le |S| + |Z| \le 3m + k + 2$.

$\square$

**Lemma 3.** Let $G$ be a graph and let $Z$ be the set of pendant vertices in $\hat{G}$. If $M$ is a minimum MEG-set of $\hat{G}$, then $S = M \setminus Z \subseteq V(G)$, and $S$ is a vertex cover of $G$. Moreover, $|S| = \text{meg}(\hat{G}) - (3m + 2)$.

*Proof.* Given a minimum MEG-set $M$ of $\hat{G}$, we know that all the pendant vertices must belong to $M$, that is, $Z \subseteq M$. As, from the proof of Lemma 2, we know that $|Z| = 3m + 2$, the moreover part of the proof follows assuming the main portion of the statement is true.

Thus, now it remains to prove that $S = M \setminus Z \subseteq V(G)$, and $S$ is a vertex cover of $G$. By Corollary 3 we know that the neighbors of the pendant vertices cannot be part of any minimum MEG-set. Therefore, $S \subseteq V(G)$ as any vertex
which does not belong to $V(G)$ is either a pendant or adjacent to a pendant in $\hat{G}$.

Next, we are going to prove that $S$ must be a vertex cover. Observe that, two pendant vertices of $\hat{G}$ cannot monitor any edge of $G$. Moreover, as any two vertices of $G$ are connected by a 2-path through the vertex $x$, to monitor an edge $e = uv \in E(G)$ in $\hat{G}$ using two vertices from $V(G)$, the only option is to consider the vertices $u$ and $v$. On the other hand, from what we had noticed in the proof of Lemma 2, we know that, any vertex $u \in V(G)$, along with the set $Z$ of pendant vertices can monitor every edge incident to $v$ in $G$. Hence, $S$ must contain at least one end point of any edge of $G$. Thus, $S$ is a vertex cover of $G$. $\square$

**Lemma 4.** Let $G$ be a 2-degenerate sub-cubic planar graph. Then $\hat{G}$ is a 3-degenerate, 2-apex graph.

Finally, we are ready to prove the main result of this section.

*Proof of the theorem 9:* It is easy to verify (in polynomial time), whether a given set $M$ is an MEG-set. This can be done by checking the distances between pairs of vertices in the set, and then checking (and comparing) the distances after removing an edge; and repeating the same for every edge. Therefore, the problem is in NP.

However, we have shown using Lemma 2 and Lemma 3 that finding a minimum MEG-set for $\hat{G}$ is equivalent (up to polynomial reduction) to finding a minimum vertex cover for $G$. As, it is well known that the minimum vertex cover problem is NP-Hard [26] even when restricted to the family of 2-degenerate subcubic planar graphs, using Lemma 4, it follows that the MEG-SET problem is NP-complete even for the class of 3-degenerate, 2-apex graphs. $\square$

# 7 Concluding remarks

(1) In Section 2, we gave examples of graphs $G_{a,b,c,d}$ which attains $g(G_{a,b,c,d}) = a$, $eg(G_{a,b,c,d}) = b$, $seg(G_{a,b,c,d}) = c$, and $meg(G_{a,b,c,d}) = d$ for “almost” all $2 \le a \le b \le c \le d$. However, for some of the combinations of $a, b, c, d$ we still do not know if an example exists or not. One problem to consider is to decide exactly for which prescribed values of $a, b, c, d$, such a graph $G_{a,b,c,d}$ exists, along with finding an explicit example.

(2) We have proved a sufficient condition for a vertex not to be part of any minimum MEG-set. An open question is to find a necessary and sufficient condition for a vertex not to be in any minimum MEG-set.

(3) In Section 5, we deal with the effects on $meg(G)$ with respect to some fundamental graph operations like clique-sums, and subdivisions. It will be interesting to perform similar studies with respect to other fundamental graph operations such as vertex deletion, edge deletion, edge contraction, etc.

(4) We have proved that the problem of finding a minimum MEG-set even for 2-apex graphs is NP-complete. Hence a natural question is to find the computational complexity of MEG-SET for planar graphs. One can ask this question for other graph families as well.
**Acknowledgements:** This work is partially supported by the following projects: IFCAM (MA/IFCAM/18/39), SERB-MATRICS (MTR/2021/000858), French government IDEX-ISITE initiative 16-IDEX-0001(CAP 20-25), ANR project GRALMECO(ANR-21-CE48-0004).

References

1. M. Atici. On the edge geodetic number of a graph. *International journal of computer mathematics*, 80(7):853–861, 2003.

2. E. Bampas, D. Bilò, G. Drovandi, L. Gualà, R. Klasing, and G. Proietti. Network verification via routing table queries. *Journal of Computer and System Sciences*, 81(1):234–248, 2015.

3. Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihalák, and L. S. Ram. Network discovery and verification. *IEEE Journal on selected areas in communications*, 24(12):2168–2181, 2006.

4. Y. Bejerano and R. Rastogi. Robust monitoring of link delays and faults in ip networks. In *IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies* (IEEE Cat. No. 03CH37428), volume 1, pages 134–144. IEEE, 2003.

5. D. Bilò, T. Erlebach, M. Mihalák, and P. Widmayer. Discovery of network properties with all-shortest-paths queries. *Theoretical computer science*, 411(14-15):1626–1637, 2010.

6. D. Chakraborty, S. Das, F. Foucaud, H. Gahlawat, D. Lajou, and B. Roy. Algorithms and complexity for geodetic sets on planar and chordal graphs. In Y. Cao, S. Cheng, and M. Li, editors, *31st International Symposium on Algorithms and Computation, ISAAC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference)*, volume 181 of *LIPIcs*, pages 7:1–7:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.

7. D. Chakraborty, H. Gahlawat, and B. Roy. Algorithms and complexity for geodetic sets on partial grids. *Theoretical Computer Science*, 979:114217, 2023.

8. G. Chartrand, F. Harary, and P. Zhang. On the geodetic number of a graph. *Networks: An International Journal*, 39(1):1–6, 2002.

9. G. Chartrand, E. M. Palmer, and P. Zhang. The geodetic number of a graph: A survey. *Congressus numerantium*, pages 37–58, 2002.

10. L. Dall'Asta, I. Alvarez-Hamelin, A. Barrat, A. Vázquez, and A. Vespignani. Exploring networks with traceroute-like probes: Theory and simulations. *Theoretical Computer Science*, 355(1):6–24, 2006.

11. T. Davot, L. Isenmann, and J. Thiebaut. On the approximation hardness of geodetic set and its variants. In C. Chen, W. Hon, L. Hung, and C. Lee, editors, *Computing and Combinatorics - 27th International Conference, COCOON 2021, Tainan, Taiwan, October 24-26, 2021, Proceedings*, volume 13025 of *Lecture Notes in Computer Science*, pages 76–88. Springer, 2021.

12. M. C. Dourado, F. Protti, D. Rautenbach, and J. L. Szwarcfiter. Some remarks on the geodetic number of a graph. *Discrete Mathematics*, 310(4):832–837, 2010.

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

14. F. Foucaud, K. Narayanan, and L. Ramasubramony Sulochana. Monitoring edge-geodetic sets in graphs. In *Algorithms and Discrete Applied Mathematics: 9th International Conference, CALDAM 2023, Gandhinagar, India, February 9–11, 2023, Proceedings*, pages 245–256. Springer, 2023.
15. R. Govindan and H. Tangmunarunkit. Heuristics for internet map discovery. In *Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies* (Cat. No. 00CH37064), volume 3, pages 1371–1380. IEEE, 2000.

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

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

18. V. Iršič. Strong geodetic number of complete bipartite graphs and of graphs with specified diameter. *Graphs and Combinatorics*, 34(3):443–456, 2018.

19. G. Joret and D. R. Wood. Complete graph minors and the graph minor structure theorem. *Journal of Combinatorial Theory, Series B*, 103(1):61–74, 2013.

20. L. Kellerhals and T. Koana. Parameterized complexity of geodetic set. *J. Graph Algorithms Appl.*, 26(4):401–419, 2022.

21. L. Lovász. Graph minor theory. *Bulletin of the American Mathematical Society*, 43(1):75–86, 2006.

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

23. N. Robertson and P. D. Seymour. Graph minors: XVII. taming a vortex. *Journal of Combinatorial Theory, Series B*, 77(1):162–210, 1999.

24. N. Robertson and P. D. Seymour. Graph minors. XX. wagner's conjecture. *Journal of Combinatorial Theory, Series B*, 92(2):325–357, 2004.

25. A. Santhakumaran and J. John. Edge geodetic number of a graph. *Journal of Discrete Mathematical Sciences and Cryptography*, 10(3):415–432, 2007.

26. M. Yannakakis. Edge-deletion problems. *SIAM Journal on Computing*, 10(2):297–309, 1981.