# Bounds and extremal graphs for monitoring edge-geodetic sets in graphs

Florent Foucaud$\,{}^{a}$, Pierre-Marie Marcille$\,{}^{b}$,
Zin Mar Myint$\,{}^{c}$, R. B. Sandeep$\,{}^{c}$, Sagnik Sen$\,{}^{c}$, S
Taruni$\,{}^{c}$

$(a)$ Université Clermont Auvergne, CNRS, Clermont Auvergne INP,
Mines Saint-Étienne LIMOS, 63000 Clermont-Ferrand, France.
$(b)$ Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800,
F-33400, Talence, France.
$(c)$ Indian Institute of Technology Dharwad, India.

###### 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
parameters 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), and prove that
some classes of graphs fall within this characterization. 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 subdivisions. In both cases, we provide a lower and an upper
bound of the possible amount of changes and provide (almost) tight examples.

Keywords: Geodetic set, Monitoring edge geodetic set, $k$-clique sum,
Subdivisions, Chromatic number, Girth.

##  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 detect failures, one of the popular methods for such monitoring processes
involves setting up distance probes [3, 4, 5, 16]. 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 [12, 20], or using path-oriented
tools to monitor IP networks [5], or problems concerning network verification
[3, 4, 6]. 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 [10, 11, 15, 21], the edge-geodetic number [2, 30], the strong
edge-geodetic number [23, 27], and the distance-edge monitoring number [16].
The focus of this article is on studying the monitoring edge-geodetic number
of a graph, a concept related to the above ones and introduced in [19] (see
also [14, 22]).

###  1.1 Main definition

We deal with simple graphs, unless otherwise stated, and will use standard
graph terminology and notation according to West [31].

######  Definition 1.1.

Let $G$ be a graph. A pair of vertices $u,v\in V(G)$, or any vertex subset
$M\subseteq V(G)$ containing them, monitors an edge $e\in E(G)$ if $e$ belongs
to all shortest paths between $u$ and $v$. A _monitoring edge-geodetic set_ or
simply, an _MEG-set_ of $G$ is a vertex subset $M\subseteq V(G)$ that monitors
every edge of $G$. The _monitoring edge-geodetic number_ , denoted by
$meg(G)$, is the cardinality of a minimum MEG-set of $G$.

The notion of MEG-sets were introduced in [19], motivated by the above network
monitoring application: the vertices of the MEG-set are distance-probes, that
can measure the distance between each other. By the definition of an MEG-set,
if some edge of the network fails, then there are at least two probes whose
distance changes, and so, the system of probes is able to detect the failure.

###  1.2 Previous works

In the paper that introduced MEG-sets [19], the value of $meg(G)$, when $G$
belongs to some basic graph families, were determined. These graph families
include the family of trees, unicyclic graphs, complete graphs, complete
multipartite graphs, rectangular grids, and hypercubes. The authors of [19]
also showed a relation with the feedback edge set number $f$ and the number
$\ell$ of leaves of the graph: $meg(G)\leq 9f+\ell-8$ (for $f\geq 2$). This
was improved to $meg(G)\leq 3f+\ell+1$ (which is tight up to an additive
factor of 1) in [8]. In [22], $meg(G)$ when $G$ is the result of certain types
of graph products was studied, in particular, Cartesian products and strong
products. The case when $G$ is a corona product was studied in [14]. In [22],
it was shown that determining $meg(G)$ is an NP-complete problem. This was
refined to hold for graphs of maximum degree at most 9 in [14].

###  1.3 Related parameters

There are some network monitoring based graph parameters studied in the
literature, whose definitions are relevant in our context since they are
related to $meg(\cdot)$ (see Section 3). 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
[21] and received considerable attention since then, both from the structural
side [10, 11, 15] and from the algorithmic side [7, 25].

  * -

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. [2] and further studied from the structural angle [30] as well as
algorithmic angle [9, 13].

  * -

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 strong edge-geodetic set of $G$. This
concept was introduced in 2017 by Manuel et al. [27]. See [23] for some
structural studies, and [13] for some algorithmic results.

  * -

A distance edge-monitoring set of a graph $G$ is a vertex subset $S\subseteq
V(G)$ such that for every edge $e$ of $G$, there are two vertices $x\in S$ and
$y\in G$ for which $e$ lies on all shortest paths between $x$ and $y$. Let
$dem(G)$ be the smallest size of a distance edge-monitoring set of $G$. This
concept was introduced in 2020 by Foucaud et al. [16]. Refer to [16, 17] for
both structural and algorithmic results for this parameter.

Vertex Cover NumberMax Leaf Number Feedback Edge Set
---
Number
$meg$ Feedback Vertex Set
---
Number
Distance Edge-Monitoring
---
Number
Strong Edge-Geodetic
---
Set Number
Edge-Geodetic
---
Set Number
Geodetic Set
---
Number
Arboricity

Figure 1: Relations between the parameter $meg$ and other structural
parameters in graphs (with no isolated vertices). For the relationships of
distance edge-monitoring sets, see [16]. Edges between parameters indicate
that the value of the bottom parameter is upper-bounded by a function of the
top parameter. Figure reproduced from [14].

Apart from the above, some well-known graph parameters too have relation with
$meg(\cdot)$. See Figure 1 (reproduced from [14]) for a diagram showing the
relations between these parameters, and others.

###  1.4 Our results, and organization of the paper

  * •

In Section 3, we recall that $g(G)\leq eg(G)\leq seg(G)\leq meg(G)$ for any
connected non-trivial graph $G$ [16]. To complement our findings, we construct
examples of graphs $G_{a,b,c,d}$ having $g(G)=a,eg(G)=b,seg(G)=c$, and
$meg(G)=d$, where $a\leq b\leq c\leq d$ (and a few additional constraints). We
also show that $dem(G)<meg(G)$, and construct examples of graphs $G_{p,q}$
having $dem(G)=p$ and $meg(G)=q$, where $1\leq p<q$.

  * •

In Section 4 we prove a necessary and sufficient condition for a vertex to be
part of every MEG-set of $G$. As a corollary, we characterize graphs $G$
having $meg(G)=|V(G)|$, which answers an open question posed by Foucaud,
Krishna and Ramasubramony, Sulochana [19]. It was worth recalling that this
open question was addressed (not solved) by Haslegrave [22]. Additionally, we
also prove a sufficient condition of when a vertex is never part of any
minimum MEG-set of the graph. These results can act as fundamental tools in
the study of MEG-set and related problems.

  * •

In Section 5, we will explore the impact of the tools built in Section 4 to
expand the list of known graphs whose minimum MEG-set is the entire vertex set
(defined as _MEG-extremal_ graphs in Section 5). To be precise, we completely
characterize $meg(G)$ when $G$ is a cograph, a block graph, a well-partitioned
chordal graph, or a proper interval graph, and observe that the 2-connected
graphs from these families are MEG-extremal. Moreover, if $G$ is an MEG-
extremal graph, then the Cartesian and the strong products of $G$ with another
graph is also MEG-extremal. The former was already known due to Haslegrave
[22], we however provide a shorter proof. Furthermore, we also show that the
tensor product of two MEG-extremal graphs is MEG-extremal.

  * •

In Section 6, we show that $meg(G)\leq\frac{4|V(G)|}{g-3}$, where $g\geq 4$
denotes the girth of $G$. As a consequence, we show that any vertex cover is
an MEG-set for a graph having girth at least $5$. Later we also prove a
refinement of the main result of this section using the chromatic number of
$G$.

  * •

In Section 7, 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 8, we share our concluding remarks which also contain suggestions
for future works in this direction.

Note: A preliminary version of this article was published in the proceedings
of the CALDAM 2024 conference [18]. This version contains an extended
introduction, all the proofs missing in the conference paper, extensions of
the results, additional results, and a corrected version of Theorem 6.1.

##  2 Preliminary results

Right before we proceed with our contributions, let us recall a few results
from [19] since we think they will give a proper initial insight into the
notion of MEG-set, and will also be used on several occasions throughout this
work.

A vertex is simplicial if its neighborhood forms a clique. A vertex $v$ of a
graph $G$ is pendent vertex if it is of degree 1.

######  Lemma 2.1 (Lemma 2.1 of [19]).

In a graph $G$ with at least one edge, any simplicial vertex belongs to any
edge-geodetic set and thus, to any MEG-set of $G$.

It is easy to observe from Lemma 2.1 that all pendent vertices of a graph $G$
are part of any MEG-set of $G$.

Two distinct vertices $u$ and $v$ are said to be open twins if $N(u)=N(v)$ and
closed twins if $N[u]=N[v]$. If $u,v$ are either closed or open twins, then we
simply call them twins.

######  Lemma 2.2 (Lemma 2.2 of [19]).

If two vertices are twins of degree at least $1$ in a graph $G$, then they
must belong to any MEG-set of $G$.

##  3 Relation between network monitoring parameters

In this section, we find examples of graphs having prescribed values of
network monitoring parameters.

###  3.1 Relation with geodetic parameters

We start with proving an if and only if condition for which a strong edge-
geodetic set is also an MEG-set.

######  Proposition 3.1.

Let $M\subseteq V(G)$ be a vertex subset of a graph $G$ and let $f$ be an
assignment of a shortest path to each pair of vertices of $M$. Then $M$ is an
MEG-set if and only if $M$, along with the assignment $f$, is a strong edge-
geodetic set for any choice of $f$.

###### Proof.

Let $M$ be an MEG-set of $G$. As all the edges of $G$ are monitored by $M$,
for each edge $e$ there exists a pair of vertices $u,v\in M$ such that $e$
lies on every shortest path between $u$ and $v$. Therefore, if we arbitrarily
assign any shortest path to each pairs of vertices of $M$, the set $M$ along
with this so-obtained assignment of shortest paths is a strong edge-geodetic
set.

On the other hand, let $M$, along with the assignment $f$, be a strong edge-
geodetic set for any choice of $f$. Now if some edge $e$ of $G$ is not
monitored, then it is possible to find an assignment of a path $P_{uv}$ to
each pair $u,v$ of vertices of $M$ such that $e$ is not contained in $P_{uv}$
for any $u,v$. This is a contradiction to our assumption. Thus, $M$ must be an
MEG-set. ∎

It is known [19] (see also Figure 1) that the following relation holds among
the geodetic parameters:

$g(G)\leq eg(G)\leq seg(G)\leq meg(G).$

Moreover, we know that for any connected graph $G\neq K_{1}$, $g(G)\geq 2$.
Therefore, it is natural to ask the question, given four positive integers
$a,b,c,d$ satisfying $2\leq a\leq b\leq c\leq 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$? The following remark captures
some basic version of this answer. Later, in Theorem 3.3 we provide a positive
answer to this question except for some specific cases.

######  Remark 3.2.

Notice that, for any complete graph $K_{n}$ on $n\geq 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 inequations.

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

$i$$i$$i$$i$$i$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{1}$ Figure 2: 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}\\}$ (the assigned shortest paths between a pair of
adjacent vertices is the edge between them, and between a pair of non-adjacent
vertices is the $2$-path through $v_{5}$) and a minimum MEG-set of $G$ is
$\\{v_{1},v_{2},v_{3},v_{4},v_{5}\\}$.

######  Theorem 3.3.

For any positive integers $4\leq a\leq b\leq c\leq d$, except for $d=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},\cdots,w_{b-a}$. Moreover, we add some edges in
such a way that the set

$W=\\{w_{1},w_{2},\cdots,w_{b-a}\\}$

becomes a clique. We also add the edge $z_{2}w_{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 subdivisions as $v_{1},v_{2},\cdots,v_{c-b+1}$. The set of vertices
created by the subdivisions is given by

$V=\\{v_{1},v_{2},\cdots,v_{c-b+1}\\}.$

$u_{3}$$u_{2}$$u_{1}$$y$$v_{1}$$v_{c-b+1}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$$x^{\prime}_{3}$$x^{\prime\prime}_{3}$$x^{\prime}_{6}$$x^{\prime}_{r-1}$$x_{r-1}$$x_{r-2}$$x_{r}$$u_{a-3}$$z_{1}$$z_{2}$$u_{a-2}$$u_{a-1}$$w_{1}$$w_{2}$$w_{b-a}$
Figure 3: The structure of $G_{a,b,c,d}.$

In the third phase of the construction, we add $(a-3)$ pendent neighbors
$u_{1},u_{2},\cdots,u_{a-3}$ to $y$, and one pendent neighbor $u_{a-2}$ to
$z_{1}$. Moreover, we attach a long path $x_{1}x_{2}\cdots x_{r}u_{a-1}$ with
the vertex $x_{1}$, where $u_{a-1}$ is a pendent vertex and
$r=3\left\lfloor\frac{d-c}{2}\right\rfloor+1$. Next we will add a false twin
$x^{\prime}_{3i}$ to the vertices of the form $x_{3i}$ for all
$i\in\left\\{1,2,\cdots,\left\lfloor\frac{d-c}{2}\right\rfloor\right\\}$.
Additionally, if $(d-c)$ is odd, then we will add another twin
$x^{\prime\prime}_{3}$ to the vertex $x_{3}$. For convenience, let

$U=\\{u_{1},u_{2},\cdots,u_{a-1}\\}$

denote the set of all pendent vertices and

$X=\left\\{x_{3i},x^{\prime}_{3i}~{}|~{}i=1,2,\cdots,\left\lfloor\frac{d-c}{2}\right\rfloor\right\\}\cup\\{x^{\prime\prime}_{3}\\}$

denote the set of all degree $2$ vertices on the paths connecting $x_{1}$ and
$u_{a-1}$.

Note that, $x^{\prime\prime}_{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. 3 for a pictorial reference).

As $U$ is the set of all pendents, we know that it will be part of any
geodetic set, edge-geodetic set, strong edge-geodetic set, and monitoring
edge-geodetic set by Lemma 2.1. 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})=|U|+|\\{z_{2}\\}|=(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_{2}w_{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})=|U|+|W|+|\\{z_{2}\\}|=(a-1)+1+(b-a)=b.$

We know that the vertices of $U$ are 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})=|U|+|W|+|V|=(a-1)+(b-a)+(c-b+1)=c.$

Finally, for any MEG-set, we have to take the vertices of $U$ (as they are
pendents), the vertices of $W$ (to monitor the edges of the clique $W$), the
vertices of $X$ (as they are twins, see Lemma 2.2). 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})=|U|+|W|+|V|+|X|=(a-1)+(b-a)+(c-b+1)+2\left\lfloor\frac{d-c}{2}\right\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.2 Relation with distance-edge monitoring sets

Observe that the concept of MEG-set is closely related to that of distance-
edge monitoring set. Notice that, MEG-sets are particular types of distance-
edge monitoring sets (see the definition of distance-edge monitoring set in
Subsection 1.1), and hence we have $dem(G)\leq meg(G)$. However, we show that
this inequality is strict.

######  Lemma 3.4.

For any graph $G$ having at least one edge, we have $dem(G)<meg(G)$.

###### Proof.

Let $M$ be a minimum MEG-set of $G$. We claim that $M\setminus\\{x\\}$ for any
$x\in M$ is a distance-edge monitoring set of $G$. This is correct as any edge
of $G$ is monitored by two vertices of $M$, and at least one of them must
belong to $M\setminus\\{x\\}$. Thus $dem(G)\leq|M|-1<meg(G).$ ∎

In view of the above lemma, given any two positive integers $p<q$, we prove
the existence of a graph $G_{p,q}$ satisfying $dem(G_{p,q})=p$ and
$meg(G_{p,q})=q.$ Note that it is possible to have $dem(G)=1$ for a graph $G$,
(for example paths [16]). Whereas $meg(G)\geq 2$ for all graphs $G$ having at
least one edge.

######  Theorem 3.5.

For any positive integers $1\leq p<q$, there exists a connected graph
$G_{p,q}$ with $dem(G_{p,q})=p$ and $meg(G_{p,q})=q.$

###### Proof.

We provide two separate constructions for the proof. One for the case when
$p=1$, and the other for the case when $p\geq 2$.

Case 1: When $1=p<q$: Consider the star graph $K_{1,q}$ with partite sets
$\\{y\\}$ and $\\{u_{1},u_{2},\cdots u_{q}\\}$. Notice that $\\{y\\}$ is a
minimum distance-edge monitoring set of $G$ [16]. Thus
$dem(G_{p,q})=dem(K_{1,q})=1=p$. On the other hand, the set of all leaves,
that is, $\\{u_{1},u_{2},\cdots u_{q}\\}$ is a minimal MEG-set [19]. Hence
$meg(G_{p,q})=meg(K_{1,q})=q$.

Case 2: When $2\leq p<q$: Let $u_{1},u_{2},\cdots u_{p+1}$ be the vertices of
a complete graph $K_{p+1}$. We add $(q-p)$ pendent vertices in the
neighborhood of $u_{1}$. The so-obtained graph is $G_{p,q}$. We know that a
minimum distance-edge monitoring set of $G_{p,q}$ is
$\\{u_{2},u_{3},\cdots,u_{p+1}\\}$ [16], and a minimum MEG-set of this graph
is $\\{v_{1},v_{2},\cdots v_{q-p},u_{2},u_{3},\cdots u_{p+1}\\}$ [19]. Hence
$meg(G_{p,q})=p$ and $meg(K_{1,q})=q$. ∎

##  4 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 [19] 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. An induced $2$-path of a graph $G$ is an ordered set of
three vertices $u,v,x$ such that $u,x$ are adjacent to $v$ while $u$ is not
adjacent to $x$.

######  Theorem 4.1.

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 for any vertex $x\in N(v)$, 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 that, 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
an 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 $v$ belongs
to every MEG-set of $G$ by Lemma 2.1. On the other hand, if there exists an
induced $2$-path of the form $uvx$, then according to our assumption, there
exists a $4$-cycle of the form $uvxwu$. Assume there exist $a,b$ two vertices
of $G$ monitoring the edge $uv$ (where $a$ and $u$ could be the same vertex).
We consider a shortest path from $a$ to $b$ that we denote $P$, where
$P=a\dots uvx\dots b$ (where $x$ and $b$ could be the same vertex). Note that
$P^{\prime}=a\dots uwx\dots b$ is another shortest path from $a$ to $b$. Hence
$a,b$ do not monitor the edge $uv$, which implies that $v$ has to be part of
every MEG-set. This concludes the proof. ∎

An immediate corollary characterizes all graphs $G$ with $meg(G)=|V(G)|$. This
answers an open question asked in [19].

######  Corollary 4.2.

Let $G$ be a graph of order $n$. Then, $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 4.1, since if there exists $u\in V(G)$
that does not fulfill the condition, then $V(G)\setminus\\{u\\}$ would be an
MEG-set. ∎

A universal vertex $u$ of a graph $G$ is a vertex that is adjacent to every
vertex except itself in $G$.

######  Corollary 4.3.

Let $G$ be a graph with a universal vertex $u$. Then any vertex $v\neq u$ is
in every MEG-set of $G$. In particular, if $G$ has $n$ vertices, then
$meg(G)\geq n-1$.

###### Proof.

Since $u$ is a universal vertex, for any $v,x\in V(G)$, $uvx$ is never an
induced $2$-path as $u,x$ are adjacent. Therefore, every vertex $v\neq u$
satisfies the necessary condition for being part of every MEG-set of $G$
according to Theorem 4.1. ∎

The girth of a graph is the length of its smallest cycle.

######  Corollary 4.4.

Let $G\neq K_{1},K_{2}$ be a connected graph with girth at least $5$. If $G$
has $n$ vertices, then $meg(G)\leq n-1$.

###### Proof.

Notice that, if a vertex $v$ of $G$ satisfies the condition of Theorem 4.1,
then either $v$ has to be part of a $3$-cycle, or a $4$-cycle, or $v$ is a
pendent vertex. As $G$ has girth at least $5$, it cannot contain any $3$-cycle
or $4$-cycle. Thus, if $G$ has $meg(G)=n$, then all vertices of $G$ are
pendent vertices. This is only possible when $G=K_{2}$, which is not possible
due to our assumption. Thus, not every vertex of $G$ can satisfy the condition
of Theorem 4.1. Hence, $meg(G)\leq n-1$. ∎

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, and can be seen as an edge-
version of Lemma 2.3 in [14].

A cut-edge of a graph $G$, is an edge $e$ such that $G-e$ has more components
than $G$.

######  Proposition 4.5.

Let $H$ be such a connected induced subgraph of $G$ that any edge incident to
a vertex of $H$ is a cut-edge of $G$. Then any vertex of $H$ is either a
vertex having degree $1$, or is never part of any minimum MEG-set.

###### Proof.

First of all, note that if $H=G$, then the condition that any edge $e\in E(H)$
is a cut-edge implies that the graph $G-e$ is disconnected. This implies that
$G$ is a tree, hence there is a unique minimum MEG-set, and it is exactly the
leaves of $G$ [19].

Thus, we can now assume that $H\neq G$, and that for any edge $e\in E(H)$, the
graph $G-e$ is disconnected. Note that the last condition implies that $H-e$
is also disconnected for any $e\in E(H)$, and hence $H$ is an induced tree.

We claim that if $C$ is a connected component of $G-H$, then there exists
exactly one vertex $u\in V(H)$ adjacent to a vertex of $C$, and that $u$ is
adjacent to no other vertex of $C$. To prove our claim, first assume that
there exist two distinct vertices $u,u^{\prime}\in V(H)$ adjacent to some
vertices of $C$. Since $H$ is connected, there exists a path from $u$ to
$u^{\prime}$ in $H$. For any edge $e$ on this path, $G-e$ is connected since
there is a path from $u$ to $u^{\prime}$ using only vertices of $C$ because
$C$ is a connected component of $G-H$, which is a contradiction. Thus, if $C$
is a connected component of $G-H$, then there exists at most one vertex of
$u\in H$ adjacent to a vertex of $C$, and that $u$ is adjacent to no other
vertex of $C$.

Assume that there exists a minimum MEG-set $M$ of $G$, and a vertex $u$ of
degree at least $2$ in $V(H)\cap M$. Let $e$ be an edge of $G$ such that $e$
is not monitored by $M-u$. If $e\in E(H)$, then it lies on the shortest path
between two leaves of $H$ that we denote $x$ and $y$. Now, either $x$ is of
degree $1$ in G, or there exists a connected component $C_{x}$ such that $x$
is adjacent to exactly one vertex of $C_{x}$. Moreover, it is easy to check
that there exists $x^{\prime}\in M\cap C_{x}$, otherwise no edge of $C_{x}$ is
monitored by $M$. The exact same argument applies to $y$, and hence the edge
$e$ is monitored by $M-u$.

If $e\in E(G-H)$, let us denote $C_{e}$ as the connected component of $G-H$
that contains $e$. Then $e$ is monitored by $u$ and a vertex of $C_{e}$. Since
$H$ is a tree, $u$ lies on the shortest path between two leaves of $H$, one of
them being adjacent to exactly one vertex of $C_{e}$. It is easy to observe
that $e$ is monitored by $M-u$, which concludes the proof. ∎

######  Corollary 4.6.

Let $G\neq K_{2}$ be a connected graph. Let $v$ be a vertex of $G$ having a
pendent neighbor $u$. Then $v$ is never part of any minimum MEG-set of $G$.

###### Proof.

The proof follows directly from Proposition 4.5 as a special case where
$H=\\{uv\\}$. ∎

######  Remark 4.7.

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

##  5 MEG-extremal graphs

An MEG-extremal graph $G$ is a graph having $meg(G)=|V(G)|$. In [14, 19], the
following families of _MEG-extremal_ graphs were presented: complete graphs,
complete multipartite graphs (except stars), and hypercubes. In [22], the
author showed that for any MEG-extremal graph $G$ and any graph $H$, both the
Cartesian product and the strong product of $G$ and $H$ are MEG-extremal
graphs.

In this section we extend the same lines of work, primarily using the tools
built in Section 4. We organize the section in two subsections. In the first
subsection we provide complete characterization of $meg(G)$ when $G$ belongs
to the families of cographs, block graphs, well-partitioned chordal graphs,
split graphs, and proper interval graphs. Using our characterization we then
conclude that the $2$-connected graphs in the above mentioned families are
MEG-extremal. In the second subsection we present a short proof of a result
from [22] where we show that the Cartesian product and the strong product of
an MEG-extremal graph with any other graph is also MEG-extremal. Moreover, we
show that the tensor product of two MEG-extremal graphs is always MEG-
extremal.

###  5.1 Graph families

We start by recalling a useful lemma from [19] on cut-vertices.

######  Lemma 5.1.

(Lemma 2.3 of [19]) Let $G$ be a graph, and $u$ be a cut-vertex of $G$. Then
$u$ is never part of any minimal MEG-set of $G$.

A cograph $G$ is a graph which does not contain any induce path on $4$
vertices, that is, an induced $P_{4}$. A complete join of two graphs $G_{1}$
and $G_{2}$ is the graph $G$ obtained by adding an edge between each vertex of
$G_{1}$ and each vertex of $G_{2}$.

######  Theorem 5.2.

Let $G$ be a connected cograph on $n$ vertices. Then either $G$ has a cut-
vertex and $meg(G)=n-1$, or else $meg(G)=n$.

###### Proof.

First assume that $G$ has a cut vertex $u$. Note that, $G-u$ has at least two
components. Observe that $u$ must be a universal vertex as otherwise it is
possible to find an induced $P_{4}$. Thus, $u$ must be the only cut-vertex of
$G$. Hence, by Corollary 4.3 and Lemma 5.1 $meg(G)=n-1$.

A $2$-connected cograph is of diameter at most $2$. Take any vertex $v$ and
any of its neighbors $u$. If there is an induced $2$-path of the form $uvx$ in
$G$, then by $2$-connectedness there exists an induced path $P$ connecting $u$
and $x$ which is internally vertex disjoint with $uvx$. However, $P$ must have
less than $4$ vertices, and thus, either $P$ is an edge, or an induced
$2$-path. Therefore, $v$ must be part of every MEG-set of $G$ according to
Theorem 4.1. ∎

A block graph $G$ is a graph whose $2$-connected components are cliques.

######  Theorem 5.3.

Let $G$ be a block graph with $k$ cut-vertices. If $G$ has $n$ vertices, then
$meg(G)=n-k$.

###### Proof.

In a block graph, a vertex is either simplicial or a cut-vertex. Hence, the
result follows from Lemma 2.1 and Lemma 5.1. ∎

A graph $G$ is a well-partitioned chordal graph [1] if its vertex set can be
partitioned into cliques $C_{1},C_{2},\ldots,C_{\ell}$ that satisfies the
following properties:

  1. (i)

The cliques $C_{1},C_{2},\ldots,C_{\ell}$ are called bags.

  2. (ii)

Two bags $C_{i}$ and $C_{j}$ are non-adjacent if there is no edge with one end
point in $C_{i}$ and the other in $C_{j}$.

  3. (iii)

Two bags $C_{i}$ and $C_{j}$ are adjacent if the edges between $C_{i}$ and
$C_{j}$ induce a complete bipartite graph.

  4. (iv)

Two bags are either adjacent or non-adjacent and the graph obtained by
considering bags as vertices with the above-mentioned adjacency rule is a
tree.

######  Theorem 5.4.

Let $G$ be a well-partitioned chordal graph with $k$ cut-vertices. If $G$ has
$n$ vertices, then $meg(G)=n-k$.

###### Proof.

Let $v$ be a vertex of $G$ which is neither a cut-vertex nor a simplicial
vertex. It is enough to show that there exists a neighbor $u$ of $v$ such that
any induced $2$-path of the form $uvx$ is part of a $4$-cycle due to Lemmas
2.1 and 5.1. Assume that $v$ belongs to the bag $C_{i}$.

Note that, as $v$ is not a simplicial vertex, $C_{i}$ must contain at least
one more vertex in it, say $u$. Suppose $uvx$ is an induced $2$-path. As $u$
and $x$ are non-adjacent, $x$ must belong to a different bag $C_{j}$.
Moreover, as $v$ is not a cut vertex, there must be another vertex $w$ in
$C_{i}$ which has an edge with a vertex of $C_{j}$. Thus, due to the
definition of a well-partitioned chordal graph, $w$ must be adjacent to both
$u$ and $x$. That is, $uvxwu$ is a $4$-cycle. Hence, $v$ must be part of all
MEG-sets of $G$ due to Theorem 4.1. ∎

A split graph $G$ is graph whose vertices can be partitioned into a clique and
an independent set.

######  Corollary 5.5.

Let $G$ be a split graph with $k$ vertices having a pendent neighbor. If $G$
has $n$ vertices, then $meg(G)=n-k$.

###### Proof.

Let $G$ be a split graph on $n$ vertices with $k$ vertices having a pendent
neighbor. Suppose that $G$ can be partitioned into a clique $C$ and an
independent set $I$. Now consider $C$ as one bag, and each vertex of $I$ as a
bag. This shows that $G$ is a well-partitioned graph as well. The proof
follows from Theorem 5.4 observing that the only cut-vertices in a split graph
are those having a pendent neighbor. ∎

An interval graph $G$ is graph whose vertices correspond to intervals, and two
vertices are adjacent if and only if their corresponding intervals intersect.
Moreover, if it is possible to assign an interval to each vertex of $G$ in
such a way that none of the intervals contains another interval, then $G$ is a
proper interval graph.

######  Theorem 5.6.

Let $G$ be a proper interval graph with $k$ cut-vertices. If $G$ has $n$
vertices, then $meg(G)=n-k$.

###### Proof.

Let $G$ be a proper interval graph on $n$ vertices with $k$ cut-vertices. For
any vertex $z$ in $G$, let us denote its corresponding interval by
$[l_{z},r_{v}]$ where $l_{z}$ denotes the left endpoint of the interval and
$r_{z}$ denotes the right endpoint of the interval. As $G$ is a proper
interval graph, it is possible to provide a total ordering $\prec$ on the
vertices of $G$ by defining $z\prec z^{\prime}$ if $l_{z}<l_{z^{\prime}}$.
Observe that, as $G$ is a proper interval graph, $l_{z}<l_{z^{\prime}}$ if and
only if $r_{z}<r_{z^{\prime}}$.

Let $v$ be a vertex of $G$ which is neither a cut-vertex nor a simplicial
vertex. It is enough to show that there exists a neighbor $u$ of $v$ such that
any induced $2$-path of the form $uvx$ is part of a $4$-cycle due to Lemmas
2.1 and 5.1.

As $v$ is not a simplicial vertex, $v$ has neighbors which intersects $l_{v}$,
and neighbors which intersects $r_{v}$. Let $L_{v}$ denote the set of all
neighbors $y$ of $v$ such that $y\prec v$. Let $u$ be the maximum element of
$L_{v}$ with respect to $\prec$. We will show that, any induced $2$-path of
the form $uvx$ must be part of a $4$-cycle.

Let $uvx$ be an induced $2$-path. Notice that we must have $u\prec v\prec x$.
As $v$ is not a cut-vertex, there exists an induced path $P=uw_{i}w_{2}\ldots
w_{\ell}x$ connecting $u$ and $x$ which does not contain the vertex $v$.
Notice that as $P$ is an induced path, we must have

$u\prec w_{1}\prec w_{2}\cdots\prec w_{\ell}\prec x.$

That means, every $w_{i}$ is a neighbor of $v$. Moreover, due to the
maximality of $u$, we must have $v\prec w_{1}$. That means $w_{1}$ intersects
$r_{v}$, and hence intersects $[l_{x},r_{x}]$. Hence, $uvxwu$ is a $4$-cycle.
∎

The results proved in this section together implies the following theorem:

######  Theorem 5.7.

If $G$ is a $2$-connected cograph, block-graph, well-partitioned chordal
graph, split graph, or proper interval graph, then $G$ is MEG-extremal.

######  Remark 5.8.

As split graphs are a subclass of well-partitioned chordal graphs, it was not
necessary to mention them separately in Theorem 5.7. However, we still do so
keeping as split graphs are a well-known class of graphs.

Figure 4: A $2$-connected interval graph with a non-extremal MEG-set. Note
that the set of all vertices except the universal vertex is an MEG-set.

######  Remark 5.9.

A natural question to ask is whether we can include superclasses of the graph
families mentioned in Theorem 5.7. In Figure 4 we provide example of a
$2$-connected interval graph which is not MEG-extremal. As interval graphs are
also chordal graphs, we cannot hope to extend Theorem 5.7 to the family of
interval graphs or chordal graphs.

###  5.2 Graph products

Let $G$ and $H$ be two graphs. Now we are going to define three (product)
graphs, each on the set of vertices

$V(G)\times V(H)=\\{(a,b):a\in V(G)\text{ and }b\in V(H)\\}.$

The strong product of $G$ and $H$, denoted by $G\boxtimes H$, has the
following adjacency rule: two vertices $(a,b)$ and $(a^{\prime},b^{\prime})$
are adjacent if and only if one of the following conditions are satisfied: (i)
$a=a^{\prime}$ and $bb^{\prime}\in E(H)$, (ii) $aa^{\prime}\in E(G)$ and
$b=b^{\prime}$, (iii) $aa^{\prime}\in E(G)$ and $bb^{\prime}\in E(H)$.

The Cartesian product of $G$ and $H$, denoted by $G\Box H$, has the following
adjacency rule: two vertices $(a,b)$ and $(a^{\prime},b^{\prime})$ are
adjacent if and only if either $a=a^{\prime}$ and $bb^{\prime}\in E(H)$, or
$aa^{\prime}\in E(G)$ and $b=b^{\prime}$.

The tensor product of $G$ and $H$, denoted by $G\Box H$, has the following
adjacency rule: two vertices $(a,b)$ and $(a^{\prime},b^{\prime})$ are
adjacent if and only if $aa^{\prime}\in E(G)$ and $bb^{\prime}\in E(H)$.

Our next result provides a shorter proof of Corollary 2 of [22].

######  Theorem 5.10 ([22]).

Let $G$ be an MEG-extremal graph and let $H$ be any graph. Then their
Cartesian product $G\Box H$ and strong product $G\boxtimes H$ are both MEG-
extremal.

###### Proof.

We prove this equality for the Cartesian product $G\Box H$ first. Let $(a,b)$
be a vertex of $G\Box H$. Since $G$ is MEG-extremal, by Theorem 4.1, for the
vertex $a\in V(G)$, there exists $u\in V(G)$ such that all induced $2$-path
$uvx$ is part of a $4$-cycle. We will show that, all induced $2$-path of the
form $(u,b)(a,b)(x,y)$ is part of a $4$-cycle in $G\Box H$. Since $(a,b)$ is
adjacent to $(x,y)$, we have the following cases:

  * •

Let $ax\in E(G)$ and $b=y$. First notice that if $(u,b)(a,b)(x,y)$ is an
induced $2$-path, $(u,b)$ and $(x,y)$ are not adjacent. Since $b=y$, the
vertices $x,u$ are not adjacent in $G$. Thus, $uax$ is an induced $2$-path in
$G$. This implies that there exists a $w\in V(G)$ such that $uaxwu$ is a
$4$-cycle in $G$. Hence, observe that $(w,b)$ is adjacent to both $(u,b)$ and
$(x,y)$.

  * •

Let $a=x$ and $by\in E(H)$. In this case note that the vertex $(u,y)$ is
adjacent to both $(u,b)$ and $(x,y)$.

Thus, by Theorem 4.1, $(a,b)$ is in every MEG-set of $G\boxtimes H$, and hence
$G\boxtimes H$ is MEG-extremal.

For proving that the strong product $G\boxtimes H$ is also MEG-extremal, we
may use consider the above two cases first, which are exactly similar. That
apart, we need to consider a third case, which is as follows.

  * •

Let $ax\in E(G)$ and $by\in E(G)$. We know that there exists a vertex $w\in
V(G)$ such that $uaxw$ is a $4$-cycle in $G$. Then observe that $(w,y)$ is
adjacent to both $(u,b)$ and $(x,y)$.

Thus, by Theorem 4.1, $(a,b)$ is in every MEG-set of $G\Box H$, and hence
$G\Box H$ is MEG-extremal. ∎

######  Theorem 5.11.

Let $G,H$ be two MEG-extremal graphs. Then their tensor product $G\times H$ is
also MEG-extremal.

###### Proof.

Let $(a,b)$ be a vertex of $G\times H$. As $G$ is MEG-extremal, there exists a
$u\in V(G)$ such that any induced $2$-path of the form $uax$ is part of a
$4$-cycle $uaxwu$ in $G$. Similarly, as $H$ is MEG-extremal, there exists a
$v\in V(H)$ such that any induced $2$-path of the form $vby$ is part of a
$4$-cycle $vbyzv$ in $H$.

Let us consider an induced $2$-path of the form $(u,v)(a,b)(x,y)$ in $G\times
H$. Notice that at least one of $uax$ and $vby$ is an induced $2$-path in $G$
or $H$, respectively. If both $uax$ and $vby$ are induced $2$-paths, then due
to the observations noted in the last paragraph, there exists $w$ that is
adjacent to both $u,x$ in $G$ and there exists $z$ that is adjacent to both
$v,y$ in $H$. Hence, $(w,z)$ is adjacent to both $(u,v)$ and $(x,y)$.
Otherwise, without loss of generality, we assume that $uax$ is an induced two
path and consider $w$ adjacent to both $u,x$ in $G$, and observe that
$(w,v^{\prime})$ is adjacent to both $(u,u^{\prime})$ and $(x,y)$, which
concludes the proof. ∎

######  Remark 5.12.

One can check that the tensor product of an MEG-extremal graph with any graph
does not always yield an MEG-extremal graph. For example, the tensor product
of the MEG-extremal graph $K_{2}$ and the path $P_{3}$ on $3$ vertices (see
Figure 5) is not MEG-extremal.

$(u,a)$$(u,b)$$(u,c)$$(v,a)$$(v,b)$$(v,c)$ Figure 5: The tensor product of a
$K_{2}$ graph $uv$ and the $P_{3}$ graph $abc$. Here, the set of degree 1
vertices is a MEG-set.

##  6 Graphs of given girth

Due to Proposition 4.5, it makes sense to study connected graphs with minimum
degree $2$. In Corollary 4.4, we noted that, if $G$ has girth $5$ or more,
then $G$ cannot be MEG-extremal. Therefore, it is natural to wonder whether
$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. The following bound is meaningful for graphs of girth at least 8.
Note that, as mentioned in the introduction, an incorrect version of this
bound appeared in the conference version of this paper [18].

######  Theorem 6.1.

Let $G$ be a $2$-connected graph with girth $g$ at least $4$. If $G$ has $n$
vertices, then $meg(G)\leq\frac{4n}{g-3}.$

###### Proof.

Let $G$ be a $2$-connected graph on $n$ vertices with girth $g\geq 4$. 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 distance at
least $\frac{g-3}{4}$ from any 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$. We want to note that $M$ can also be
obtained by applying a greedy algorithm to find a maximal independent set in
the $(\frac{g-3}{4})$-th power of $G$.

Next, we will show that $M$ is indeed an MEG-set of $G$. Let $uv$ be an
arbitrary edge of $G$. Note that, the distance between $u$ (resp., $v$) and
the set $M$ is strictly less than $\frac{g-3}{4}$ due to the way we
constructed $M$. Also, the nearest vertex to $u$ in $M$ and the nearest vertex
to $v$ in $M$ are distinct as otherwise it will imply a cycle of length
strictly less than $g$, contradicting the girth condition on $G$. Therefore,
without loss of generality, we may assume that there exists $u^{\prime}\in M$
such that $d(u,u^{\prime})\leq\frac{g-3}{4}$ and
$d(v,u^{\prime})>d(u,u^{\prime})$. Moreover, let $v^{\prime}$ be the vertex of
$M$ closest to $v$. Let $P_{1}$ be a shortest path connecting $u^{\prime}$ and
$u$, and $P_{2}$ be a shortest path connecting $v$ and $v^{\prime}$. Let $P$
be the path obtained by concatenation of the path $P_{1}$, the edge $uv$, and
the path $P_{2}$. Note that the length of $P$ is at most

$\frac{g-3}{4}+1+\frac{g-3}{4}=\frac{g-1}{2}.$

Therefore, $P$ is the unique shortest path connecting $u^{\prime}$ and
$v^{\prime}$, as otherwise it will imply that $u^{\prime}v^{\prime}$ are part
of a cycle of length strictly less than $g$, contradicting the girth condition
on $G$. Hence, $u^{\prime}v^{\prime}$ monitors the edge $uv$.

Now we are left with counting the cardinality of $M$. For any vertex $u\in M$,
let $S_{u}$ be the set of all vertices that are at distance at most $\ell$
from $u$, where $\ell$ is the biggest integer such that a vertex of $G$ is at
distance $\ell$ or less from at most one vertex of $M$. Notice that, for any
two vertices $u,v\in M$, $S_{u}\cap S_{v}=\emptyset$, hence a path connecting
$u$ and $v$ will be of length at least $2\ell+1$. As any two vertices of $M$
are at distance at least $\frac{g-3}{4}$ from one another, then

$2\ell+1\geq\frac{g-3}{4}\implies\ell\geq\frac{g-7}{8}.$

As $G$ is a $2$-connected graph, each vertex $v$ of $M$ is part of a cycle
which implies that $|S_{v}|\geq 2\ell+1$ (counting $v$ itself too). Therefore,
we must have

$n=|V(G)|\geq|M|(2\ell+1)\geq|M|(\frac{2(g-7)}{8}+1)\implies|M|\leq\frac{4n}{g-3}.$

This completes the proof. ∎

######  Remark 6.2.

As the girth can be considered as a measure of sparseness of a graph, the
above result shows that $meg(G)$ has a stricter upper bound when 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.

We now prove that $meg(G)$ of a sparse graph $G$ is upper bounded by a
function of its chromatic number $\chi(G)$.

######  Theorem 6.3.

For $G$ a connected graph of minimum degree $2$ and girth at least $5$, any
vertex cover of $G$ is an MEG-set.

###### Proof.

Let $G$ be a connected graph having minimum degree at least $2$ and $n$
vertices. Let $I$ be an independent set. Since any vertex cover of $G$ is the
complementary of an independent set, it is enough to show that
$M=V(G)\setminus I$ is an MEG-set of $G$.

Let $uv$ be any edge of $G$. If $u,v\not\in I$, then that implies $u,v\in M$,
and thus, $uv$ is monitored. If $u\in I$ and $v\not\in I$, then $v\in M$. As
the minimum degree of $G$ is at least $2$, $u$ must have a neighbor $w$ (say)
other than $v$. Note that as $I$ is an independent set, $w$ cannot belong to
$I$. This means, in particular, $w\in M$. Notice that $wuv$ must be the unique
shortest path joining $w$ and $v$ as the girth of $G$ is at least $5$, and
thus $uv$ is monitored. ∎

######  Corollary 6.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\left(\frac{\chi(G)-1}{\chi(G)}\right).$

###### Proof.

If $G$ is a connected graph with $\chi(G)=k$ and $n$ vertices, a maximum
independent set of $G$ is of size at least $\frac{n}{k}$, which immediately
yields the bound using Theorem 6.3. ∎

We prove a more general version of Corollary 6.4 for graphs that have pendent
vertices.

######  Corollary 6.5.

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

###### Proof.

We know that the pendent vertices are part of any MEG-set of $G$ by Lemma 2.1.
Now, let us remove the minimum number of vertices from $G$ to obtain a
subgraph $G^{\prime}$ which is a connected graph having minimum degree $2$ (if
possible). Notice that, to obtain $G^{\prime}$, we need to remove at least the
$\ell$ pendents. Therefore, $G^{\prime}$ will have at most $(n-\ell)$
vertices. Therefore, using Corollary 6.4 we can find an MEG-set of
$G^{\prime}$ having cardinality
$(n-\ell)\left(\frac{\chi(G)-1}{\chi(G)}\right)$ as
$\chi(G^{\prime})\leq\chi(G)$. Observe that the MEG-set of $G^{\prime}$
together with the pendent vertices of $G$ can monitor all the edges of $G$.
Therefore,

$meg(G)\leq(n-\ell)\left(\frac{\chi(G)-1}{\chi(G)}\right)+\ell=n\left(\frac{\chi(G)-1}{\chi(G)}\right)+\frac{\ell}{\chi(G)}.$

If, in case, it is not possible to obtain such a $G^{\prime}$, then we can
infer that $G$ is a forest. In that case, the set of all pendents is an MEG-
set of $G$. That means, $meg(G)\leq\ell$, which satisfies the statement
trivially. ∎

##  7 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 identifying the vertices of
$C_{1}$ with the vertices of $C_{2}$ (each vertex of $C_{1}$ is identified
with exactly one vertex of $C_{2}$).

This particular operation between two graphs is a fundamental operation in
graph theory, and is used for characterizing chordal graphs, maximal planar
graphs, $K_{5}$-minor-free graphs, etc. Some variants of the definition
requires deletion of all or some edges of the clique which maybe important in
the context of the problem solved. For example, in the context of the
illustrious graph structure theorem [24, 28], it is allowed to delete some
edges of the clique obtained by identification. In our context, as MEG-sets do
not interact well with edge deletion, we investigate the changes in $meg(G)$
with respect to the clique-sum operation without edge deletion.

######  Theorem 7.1.

Let $G_{1}\oplus_{k}G_{2}$ be a $k$-clique-sum of the graphs $G_{1}$ and
$G_{2}$ for some $k\geq 2$. Then we have,

$meg(G_{1})+meg(G_{2})-2k\leq meg(G_{1}\oplus_{k}G_{2})\leq
meg(G_{1})+meg(G_{2}).$

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

###### Proof.

Let $M_{1}$ and $M_{2}$ be MEG-sets of $G_{1}$ and $G_{2}$. Observe that, the
union $M_{1}\cup M_{2}$ is an MEG-set of $G$. This implies the upper bound.

For the lower bound, first let $C=V(G_{1})\cap V(G_{2})$ be the clique of size
$k$, common to $G_{1}$ and $G_{2}$. Let $M$ be a minimum MEG-set of $G$. Note
that, $M_{1}=(M\setminus V(G_{2}))\cup C$ is an MEG-set of $G_{1}$, and
$M_{2}=(M\setminus V(G_{1}))\cup C$ is an MEG-set of $G_{2}$. Observe that,

$\displaystyle meg(G_{1})+meg(G_{2})$ $\displaystyle\leq|M_{1}|+|M_{2}|$
$\displaystyle=|(M\setminus V(G_{2}))\cup C|+|(M\setminus V(G_{1}))\cup
C|\leq|M|+2|C|$ $\displaystyle=meg(G)+2k$

This proves the lower bound.

Tightness of the upper bound: Take $G_{1}=G_{2}=K_{k}^{*}$, where $K_{k}^{*}$
denotes the graph obtained by adding a pendent neighbor to each vertex of the
complete graph $K_{k}$. Due to Corollary 4.6, $meg(G_{1})=meg(G_{2})=k$. Note
that, there is essentially a unique way to obtain a $k$-clique-sum of $G_{1}$
and $G_{2}$, and let $G=G_{1}\oplus_{k}G_{2}$ be the graph obtained after
performing the $k$-clique-sum. Observe that $G$ is the graph obtained by
adding two pendent neighbors to each vertex of the complete graph $K_{k}$.
Therefore, by Corollary 4.6,

$meg(G)=2k=k+k=meg(G_{1})+meg(G_{2}).$

Tightness of the lower bound: First we will describe the construction of a
graph $H_{k}$. To construct this graph, we start with a complete graph
$K_{k+1}$ on $(k+1)$ vertices named $v_{0},v_{1},v_{2},\cdots,v_{k}$. Next, we
add a $3$-path of the form $v_{i,1}v_{i,2}v_{i,3}v_{i}$ attached to $v_{i}$
for each $i\in\\{0,1,\cdots,k\\}$. Moreover, we add edges between the vertices
$v_{0,2},v_{1,2},\cdots,v_{k,2}$ to form a clique. Finally we subdivide each
edge of the above mentioned clique exactly once. The so obtained graph is
$H_{k}$. We take $G_{1}=G_{2}=H_{k}$. However, for convenience, the vertices
of $G_{1}$ is denoted by the original names given to the vertices of $H_{k}$,
while the vertices of $G_{2}$ is denoted by placing a “bar” over the original
names given to the vertices of $H_{k}$. That is, instead of using the names
$v_{0},v_{1},v_{3,2}$, we will use the names
$\bar{v}_{0},\bar{v}_{1},\bar{v}_{3,2}$ when we want to refer to the vertices
of $G_{2}$. Let $G=G_{1}\oplus_{k}G_{2}$ be the graph obtained by taking a
$k$-clique-sum of $G_{1}$ and $G_{2}$ on the cliques
$\\{v_{1},v_{2},\cdots,v_{k}\\}$ and
$\\{\bar{v}_{1},\bar{v}_{2},\cdots,\bar{v}_{k}\\}$.

Observe that, $H_{k}$ has $(k+1)$ pendents, and thus they are part of any MEG-
set of $H_{k}$. Next suppose that
$M^{*}=V(H_{k})\setminus\\{v_{0},v_{1},v_{0,3},v_{1,3}\\}$. Notice that, this
set is not able to monitor the edge $v_{0}v_{1}$. That means, we need to take
at least $k$ vertices, other than the $(k+1)$ pendent vertices, in any MEG-set
of $H_{k}$. On the other hand, the set obtained by the pendent vertices and
all but one vertex from the $K_{k+1}$ clique gives us an MEG-set of $H_{k}$.
Hence, $meg(H_{k})=2k+1$.

Furthermore, $G$ has exactly $(2k+2)$ pendents, and the set of all pendents of
$G$ is an MEG-set. Therefore,

$meg(G)=2k+2=(2k+1)+(2k+1)-2k=meg(G_{1})+meg(G_{2})-2k.$

This concludes the proof. ∎

Let $G$ be a graph. We obtain the graph $S^{\ell}_{G}$ 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 sparsification 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 [26, 29]. The following result proves a relation between $meg(G)$ and
$meg(S^{\ell}_{G})$.

######  Theorem 7.2.

For any graph $G$ and for all $\ell\geq 2$, we have

$1\leq\frac{meg(G)}{meg(S^{\ell}_{G})}\leq 2.$

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

###### Proof.

Let $M$ be an MEG-set of $G$. Then observe that, $M$ is also an MEG-set of
$S^{\ell}_{G}$. This proves $meg(S^{\ell}_{G})\leq meg(G)$.

On the other hand, let $M^{\prime}$ be an MEG-set of $S^{\ell}_{G}$. Now we
construct an MEG-set $M$ of $G$ using $M^{\prime}$. Let $v$ be a vertex of
$M^{\prime}$. If $v$ is also a vertex of $G$, then we put $v$ in $M$. If $v$
is not a vertex of $G$, then $v$ must be one of the vertices which was used
for subdividing an edge $e$ of $G$ to obtain $S^{\ell}_{G}$. In such a case,
we put both the end points of $e$ in $M$. Note that, the so-obtained $M$ is an
MEG-set of $G$. As $|M|\leq 2|M^{\prime}|$, we have $meg(G)\leq
2meg(S^{\ell}_{G})$. This completes the proof of the inequality.

Tightness of the lower bound: Take $G=C_{n}$, where $C_{n}$ is the cycle on
$n$ vertices for $n\geq 5$. Note that, in such a scenario, $S^{\ell}_{G}$ is
the cycle $C_{n(\ell+1)}$ on $n(\ell+1)$ vertices. We know that
$meg(G)=meg(S^{\ell}_{G})=3$ [19]. Thus, we have infinitely many examples of
$G$ where,

$\frac{meg(G)}{meg(S^{\ell}_{G})}=1.$

Asymptotic tightness of the upper bound: Let $G=P_{k}\square P_{2}$, that is
the Cartesian product of the paths $P_{k}$ (on $k$ vertices) and $P_{2}$ (on
$2$ vertices). For convenience, let us assume that $G$ is embedded on the
plane with its vertices placed on the points $(i,j)$, where
$i\in\\{0,1,\cdots,k-1\\}$ and $j\in\\{0,1\\}$. Moreover, let the vertex
placed on $(i,j)$ be denoted by $v_{i,j}$. Two vertices of this graph are
adjacent if they are at a Euclidean distance exactly $1$. We know that
$meg(G)=2k$ [19]. We will construct an MEG-set $M$ of size $(k+1)$ for
$S^{\ell}_{G}$. First of all, put the vertices $v_{0,0}$ and $v_{0,1}$ in $M$.
Let $w_{i}$ be a vertex (choose any option) on the path obtained by
subdividing the edge $v_{i,0}v_{i,1}$. Put $w_{i}$ in $M$ for all
$i\in\\{1,2,\cdots,k-1\\}$. Observe that, the so-obtained $M$ monitors
$S^{\ell}_{G}$. Therefore, $meg(S^{\ell}_{G})\leq k+1$. Hence,

$\frac{meg(G)}{meg(S^{\ell}_{G})}\leq\frac{2k}{k+1}=2-\frac{2}{k+1}.$

As $k$ tends to infinity, the ratio $\frac{meg(G)}{meg(S^{\ell}_{G})}$ tends
to the upper bound $2$. Hence the upper bound is asymptotically tight. ∎

##  8 Concluding remarks

  1. (1)

In Section 3, 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\leq a\leq b\leq c\leq 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. (2)

In Section 4, we have proved a sufficient condition for a vertex not to be
part of any minimum MEG-set. A question in this direction is to find a
necessary and sufficient condition for a vertex not to be in any minimum MEG-
set.

  3. (3)

In Section 5, we used the result of Theorem 4.1, as well as a more
comprehensive definition of MEG-extremal, to prove that several well-known
graph classes, restricted to $2$-connected graphs, are MEG-extremal. We
provide an example of a $2$-connected interval graph that is not MEG-extremal.
Thus, it will be interesting to characterize or devise efficient algorithms to
find $meg(G)$ when $G$ is an interval graph, or a chordal graph. One can also
try to extend the results of Theorem 5.2 and 5.6 to perfect graphs.

  4. (4)

In Section 7, 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.

Acknowledgements: This work is partially supported by the following projects:
IFCAM (MA/IFCAM/18/39), SERB-MATRICS (MTR/2021/000858 and MTR/2022/000692),
French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25),
International Research Center ”Innovation Transportation and Production
Systems” of the I-SITE CAP 20-25, and ANR project GRALMECO (ANR-21-CE48-0004).

## References

  * [1] J. Ahn, L. Jaffke, O. joung Kwon, and P. T. Lima.  Well-partitioned chordal graphs.  Discrete Mathematics, 345(10):112985, 2022.
  * [2] M. Atici.  On the edge geodetic number of a graph.  International journal of computer mathematics, 80(7):853–861, 2003\.
  * [3] 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.
  * [4] Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihal’ak, and L. S. Ram.  Network discovery and verification.  IEEE Journal on selected areas in communications, 24(12):2168–2181, 2006.
  * [5] 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.
  * [6] 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.
  * [7] 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.
  * [8] D. Chakraborty, F. Foucaud, and A. Hakanen.  Distance-based covering problems for graphs of given cyclomatic number.  In H. Fernau and K. Jansen, editors, Fundamentals of Computation Theory - 24th International Symposium, FCT 2023, Trier, Germany, September 18-21, 2023, Proceedings, volume 14292 of Lecture Notes in Computer Science, pages 132–146. Springer, 2023.
  * [9] D. Chakraborty, H. Gahlawat, and B. Roy.  Algorithms and complexity for geodetic sets on partial grids.  Theoretical Computer Science, 979:114217, 2023.
  * [10] G. Chartrand, F. Harary, and P. Zhang.  On the geodetic number of a graph.  Networks: An International Journal, 39(1):1–6, 2002.
  * [11] G. Chartrand, E. M. Palmer, and P. Zhang.  The geodetic number of a graph: A survey.  Congressus numerantium, pages 37–58, 2002.
  * [12] 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.
  * [13] 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.
  * [14] S. R. Dev, S. Dey, F. Foucaud, N. Krishna, and L. R. Sulochana.  Monitoring edge-geodetic sets in graphs, 2023.  arXiv preprint 2210.03774.
  * [15] 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.
  * [16] 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.
  * [17] F. Foucaud, R. Klasing, M. Miller, and J. Ryan.  Monitoring the edges of a graph using distances.  In M. Changat and S. Das, editors, Algorithms and Discrete Applied Mathematics: 6th International Conference, CALDAM 2020, IIT Hyderabad, India, February 13–15, 2020, Proceedings, pages 28–40. Springer International Publishing, 2020.
  * [18] F. Foucaud, P. Marcille, Z. M. Myint, R. B. Sandeep, S. Sen, and S. Taruni.  Monitoring edge-geodetic sets in graphs: Extremal graphs, bounds, complexity.  In S. Kalyanasundaram and A. Maheshwari, editors, Algorithms and Discrete Applied Mathematics - 10th International Conference, CALDAM 2024, Bhilai, India, February 15-17, 2024, Proceedings, volume 14508 of Lecture Notes in Computer Science, pages 29–43. Springer, 2024.
  * [19] 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.
  * [20] 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.
  * [21] F. Harary, E. Loukakis, and C. Tsouros.  The geodetic number of a graph.  Mathematical and Computer Modelling, 17(11):89–95, 1993.
  * [22] J. Haslegrave.  Monitoring edge-geodetic sets: hardness and graph products.  Discrete Applied Mathematics, 340:79–84, 2023.
  * [23] V. Iršič.  Strong geodetic number of complete bipartite graphs and of graphs with specified diameter.  Graphs and Combinatorics, 34(3):443–456, 2018.
  * [24] 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.
  * [25] L. Kellerhals and T. Koana.  Parameterized complexity of geodetic set.  J. Graph Algorithms Appl., 26(4):401–419, 2022.
  * [26] L. Lovász.  Graph minor theory.  Bulletin of the American Mathematical Society, 43(1):75–86, 2006\.
  * [27] 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.
  * [28] N. Robertson and P. D. Seymour.  Graph minors: Xvii. taming a vortex.  Journal of Combinatorial Theory, Series B, 77(1):162–210, 1999\.
  * [29] N. Robertson and P. D. Seymour.  Graph minors. xx. wagner’s conjecture.  Journal of Combinatorial Theory, Series B, 92(2):325–357, 2004\.
  * [30] A. Santhakumaran and J. John.  Edge geodetic number of a graph.  Journal of Discrete Mathematical Sciences and Cryptography, 10(3):415–432, 2007.
  * [31] D. B. West et al.  Introduction to graph theory, volume 2.  Prentice hall Upper Saddle River, 2001.