Keywords

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 [2,3,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 Sect. 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 Sect. 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 Sect. 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 Sect. 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 Sect. 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 Sect. 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, Fig. 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.    \(\square \)

Fig. 1.
figure 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\}\).

Full size image

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, \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_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 subdivisions as \(v_1, v_2, \cdots , v_{c-b+1}\). The set of these vertices created by the subdivisions is given by

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

The structure of \(G_{a,b,c,d}.\)

Full size image

In the third phase of the construction, we add \((a-3)\) pendant neighbors \(u_1, u_2, \cdots , 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, \cdots , \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, \cdots , u_{a-1}\}$$

will denote the set of all pendents and

$$X = \{x_{3i}, x'_{3i} | i = 1, 2, \cdots ,\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 \ne c+1\). This completes the proof.    \(\square \)

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. \(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 \(meg(G)=n\) can be verified in polynomial time due to Corollary 1.

Corollary 2

If \(G \ne K_2\) is a connected graph of order n and girth \(g \ge 5\), then \(meg(G) \le 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 \ge 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, \(meg(G) \le 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 \ne 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 \ne 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 \(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 meg(G), if G has girth 5 or more, cannot be equal to the order of G. 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.

Theorem 3

Let G be a connected graph having minimum degree at least 2. If G has n vertices and girth g, then \(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 \in M\). Furthermore, notice that, for two vertices \(u,v \in 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)| \ge |M| + |M|\left( \frac{g-3}{4}\right) \implies |M| \le \frac{4n}{g+1}.$$

This completes the proof.    \(\square \)

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) \le n\left( \frac{\chi (G)-1}{\chi (G)}\right) .\)

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) \le n\left( \frac{\chi (G)-1}{\chi (G)}\right) + \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^{\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 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^{\ell }_G)\).

Theorem 6

For any graph G and for all \(\ell \ge 2\), we have

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

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

Remark 3

We have observed that \(meg(S^{\ell }_G)=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.

figure a

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.

figure b

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 \(\widehat{G}\) and there by proving the equivalence of finding \(meg(\widehat{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 \(\widehat{G}\) : Given a graph G, we describe the construction of a new graph \(\widehat{G}\) based on the structure of G in the following. For each edge \(e=uv \in E(G)\), we add a 5-path \(u u' 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 \(\widehat{G}\). We refer to Fig. 3 for a pictorial reference demonstrating how one edge of G transforms in \(\widehat{G}\).

Fig. 3.
figure 3

A demonstration of the construction of \(\widehat{G}\).

Full size image

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

Lemma 1

The new edges of \(\widehat{G}\), that is, the edges from the set \(E(\widehat{G}) \setminus E(G)\), are monitored by the set of all pendant vertices of \(\widehat{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''\).

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 \(meg(\widehat{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 \(\widehat{G}\). We want to show that \(|Z| = 3m+2\), and \(S \cup Z\) is an MEG-set of \(\widehat{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 \(\widehat{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 \(\widehat{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 \(\widehat{G}\), and hence, \(meg(\widehat{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 \(\widehat{G}\). If M is a minimum MEG-set of \(\widehat{G}\), then \(S = M \setminus Z \subseteq V(G)\), and S is a vertex cover of G. Moreover, \(|S| = meg(\widehat{G})- (3m+2)\).

Proof

Given a minimum MEG-set M of \(\widehat{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 pendent 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 \(\widehat{G}\).

Next, we are going to prove that S must be a vertex cover. Observe that, two pendant vertices of \(\widehat{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 \(\widehat{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 \(\widehat{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 \(\widehat{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 sub-cubic 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. (1)

    In Sect. 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. (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. (3)

    In Sect. 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. (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.