Florent Foucaud

Krishna Narayanan

Ramasubramony S Lekshmi

Sulochana

N Krishna

Monitoring edge-geodetic sets in graphs

published or not. The documents may come

Introduction

We introduce a new graph-theoretic concept, that is motivated by the problem of network monitoring, called monitoring edge-geodetic sets. In the area of network monitoring, one wishes to detect or repair faults in a network; in many applications, the monitoring process involves distance probes [START_REF] Bampas | Network verification via routing table queries[END_REF][START_REF] Beerliova | Network discovery and verification[END_REF][START_REF] Bejerano | Robust monitoring of link delays and faults in IP networks[END_REF][START_REF] Foucaud | Monitoring the edges of a graph using distances[END_REF]. Our networks are modeled by finite, undirected simple connected graphs, whose vertices represent systems and whose edges represent the connections between them. We wish to monitor a network such that when a connection (an edge) fails, we can detect the said failure by means of certain probes. To do this, we select a small subset of vertices (representing the probes) of the network such that all connections are covered by the shortest paths between pairs of vertices in the network. Moreover, any two probes are able to detect the current distance that separates them. The goal is that, when an edge of the network fails, some pair of probes detects a change in their distance value, and therefore the failure can be detected. Our inspiration comes from two areas: the concept of geodetic sets in graphs and its variants [START_REF] Harary | The geodetic number of a graph[END_REF], and the concept of distance edge-monitoring sets [START_REF] Foucaud | Monitoring the edges of a graph using distances[END_REF][START_REF] Foucaud | Monitoring the edges of a graph using distances[END_REF].

We now proceed with some necessary definitions. A geodesic is a shortest path between two vertices u, v of a graph G [START_REF] Skiena | Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica[END_REF]. The length of a geodesic between two vertices u, v in G is the distance d G pu, vq between them. For an edge e of G, we denote by G´e the graph obtained by deleting e from G. An edge e in a graph G is a bridge if G´e has more connected components than G. The open neighborhood of a vertex v P V pGq is N G pvq " tu P V | uv P EpGqu and its closed neighborhood is the set N G rvs " N G pvq Y tvu.

Monitoring edge-geodetic sets. We now formally define of our main concept. Definition 1.1. Two vertices x, y monitor an edge e in graph G if e belongs to all shortest paths between x and y. A set S of vertices of G is called a monitoring edge-geodetic set of G ( MEG-set for short) if, for every edge e of G, there is a pair x, y of vertices of S that monitors e.

We denote by megpGq the size of a smallest MEG-set of G. We note that V pGq is always an MEG-set of G, thus megpGq is always well-defined.

Related notions.

A set S of vertices of a graph G is a geodetic set if every vertex of G lies on some shortest path between two vertices of S [START_REF] Harary | The geodetic number of a graph[END_REF]. An edge-geodetic set of G is a set S Ď V pGq such that every edge of G is contained in a geodesic joining some pair of vertices in S [START_REF] Santhakumaran | Edge geodetic number of a graph[END_REF]. A strong edge-geodetic set of G is a set S of vertices of G such that for each pair u, v of vertices of S, one can select a shortest u ´v path, in a way that the union of all these `|S| 2 ˘paths contains EpGq [START_REF] Manuel | Strong edge geodetic problem in networks[END_REF]. It follows from these definitions that any strong edge-geodetic set is an edge-geodetic set, and any edge-geodetic set is a geodetic set (if the graph has no isolated vertices). In fact, every MEG-set is a strong edge-geodetic set. Indeed, given an MEG-set S, one can choose any shortest path between each pair of vertices of S, and the set of these paths covers EpGq. Indeed, every edge of G is contained in all shortest paths between some pair of S. Hence, MEG-sets can be seen as an especially strong form of strong edge-geodetic sets.

A set S of vertices of a graph G is a distance-edge monitoring set if, for every edge e, there is a vertex x of S and a vertex y of G such that e lies on all shortest paths between x and y [START_REF] Foucaud | Monitoring the edges of a graph using distances[END_REF][START_REF] Foucaud | Monitoring the edges of a graph using distances[END_REF]. Thus, it follows immediately that any MEG-set of a graph G is also a distance-edge monitoring set of G.

Our results. We start by presenting some basic lemmas about the concept of MEG-sets in Section 2, that are helpful for understanding this concept. We then study in Section 3 the optimal value of megpGq when G is a tree, cycle, unicyclic graph, complete (multipartite) graph, hypercubes and grids. In Section 4, we show that megpGq is bounded above by a linear function of the feedback edge set number of G (the smallest number of edges of G needed to cover all cycles of G, also called cyclomatic number ) and the number of leaves of G. This implies that megpGq is bounded above by a function of the max leaf number of G (the maximum number of leaves in a spanning tree of G). These two parameters are popular in structural graph theory and in the design of algorithms. We refer to Figure 1 for the relations between parameter meg and other graph parameters. Finally, we conclude in Section 5.

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 [START_REF] Foucaud | Monitoring the edges of a graph using distances[END_REF][START_REF] Foucaud | Monitoring the edges of a graph using distances[END_REF]. Arcs between parameters indicate that the value of the bottom parameter is upper-bounded by a function of the top parameter.

Preliminary lemmas

We now give some useful lemmas about the basic properties of MEG-sets. A vertex is simplicial if its neighborhood forms a clique.

Lemma 2.1. 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.

Proof. Let us consider by contradiction an MEG-set of G that does not contain said simplicial vertex v. Any shortest path passing through its neighbors will not pass through v, because all the neighbors are adjacent, hence leaving the edges incident to v uncovered, a contradiction. Proof. For any pair u, v of open twins in G, for any shortest path passing through u, there is another one passing through v. Thus, if u, v were not part of the MEG-set, then the edges incident to u and v would remain unmonitored, a contradiction.

If u, v are closed twins, if some shortest path contains the edge uv, then it must be of length 1 and consist of the edge uv itself (otherwise there would be a shortcut). Thus, to monitor uv, both u, v must belong to any MEG-set.

The next two lemmas concern cut-vertices and subgraphs, and will be useful in some of our proofs.

Lemma 2.3. Let G be a graph with a cut-vertex v and C 1 , C 2 , . . . , C k be the k components obtained when removing v from G. If S 1 , S 2 , . . . , S k are MEG-sets of the induced subgraphs GrC 1 Y tvus, GrC 2 Y tvus, . . . , GrC k Y tvus, then S " pS 1 Y S 2 , . . . , YS k qztvu is an MEG-set of G.
Proof. Consider any edge e of G, say in C 1 . Then, there are two vertices x, y of S 1 such that e belongs to all shortest paths between x and y in G 1 " GrC 1 Y tvus. Assume first that v R tx, yu. All shortest paths between x and y in G also exist in G 1 . Thus, e is monitored by tx, yu Ď S in G. Assume next that v P tx, yu: without loss of generality, v " x. At least one edge exists in GrC 2 Y tvus, which implies that S 2 ztvu is nonempty, say, it contains z. Then, e is monitored by y and z, since z P S. Thus, S monitors all edges of G, as claimed.

Lemma 2.4. Let G be a graph and H an induced subgraph of G such that for all vertex pairs tx, yu in H, no shortest path between them uses edges in G ´H. Then, for any set S of vertices of G containing an MEG-set of H, the edges of H are monitored by S in G.

Proof. Let S be an MEG-set of G containing an MEG-set S 1 of H. Let e be an edge in H that lies on all shortest paths between some pair tx, yu of vertices of S 1 . By our hypothesis, no shortest path between x and y in G uses any edges of G ´H. Thus, the shortest paths between x and y in H are the same as in G, and therefore in G, e is also monitored by tx, yu Ď S.

Basic graph classes and bounds

In this section, we study MEG-sets for some standard graph classes.

Trees

Theorem 3.1. For any tree T with at least one edge, the only optimal MEG-set of T consists of the set of leaves of T .

Proof. The fact that all leaves must be part of any MEG-set follows from Lemma 2.1, as they are simplicial. For the other side, let L be the set of leaves of T . Let e " xy be an edge of T and consider two leaves of T , l x and l y , such that l x is closer to x than to y and that l y is closer to y than to x. We note that e belongs to the unique (shortest) path between l x and l y , thus e is monitored by L. Hence, L is an MEG-set of T . Corollary 3.2. For any path graph P n , where n ě 2, we have megpP n q " 2 This provides a lower bound which is tight for path graphs, which have order n and exactly 2 leaves. Corollary 3.3. For any tree T of order n ě 3, we have 2 ď megpT q ď n ´1.

The upper bound is tight for star graphs, which have order n and n ´1 leaves.

Cycle graphs

We introduce the following terminology from [START_REF] Epstein | The (weighted) metric dimension of graphs : hard and easy cases[END_REF]. In a graph, a vertex is a core vertex if it has degree at least 3. A leg is a (non-empty) path in a tree graph between a leaf v and a core vertex u of the graph that is closest to this leaf (note that the leg does not contain the core vertex u but the leaf v). Theorem 3.4. Given an n-cycle graph C n , for n " 3 and n ě 5, megpC n q " 3. Moreover, megpC 4 q " 4.

Proof. Let us first prove that we need at least three vertices to monitor any cycle. By contradiction, let us assume that two vertices suffice. For any arbitrary vertex pair in the cycle graph, there are two paths joining them, but there is either one single shortest path or two equidistant shortest paths between them. Thu, the edges on at least one of the two paths between the pair will not be monitored by it. Hence, we need at least three vertices in any MEG-set of C n (n ě 3).

We now prove the upper bound. Let n ě 5 or n " 3, with the vertices of C n from v 0 to v n´1 . Consider the set S " tv 0 , v t n 3 u , v t 2n 3 u u. We show that S is an MEG-set of C n . Consider every edge of C n between a vertex pair v x and v y in S, then we note that they lie on every (unique) shortest path between these vertices, which has a length at least one for n ď 5 and at least 2 otherwise, and at most X n

2

´1\ . Thus, megpC n q " 3 when n ě 5 or n " 3. In the case of C 4 , the above construction does not work. Consider a set of three vertices, say v 0 , v 1 , v 2 without loss of generality due to the symmetries of C 4 . Notice that the edge v 0 v 3 is unmonitored by this set. Thus, we have megpC 4 q " 4.

Unicyclic graphs

A unicyclic graph is a connected graph containing exactly one cycle [START_REF] Harary | Graph Theory[END_REF]. We now determine the optimal size of an MEG-set of such graphs. Theorem 3.5. Let G be a unicyclic graph where the only cycle C has length k and whose set of pendant vertices is LpGq, |LpGq| " l. Let V c be the set of vertices of C with degree at least 3. Let ppGq " 1 if GrV pCqzV c s contains a path whose length is at least

Y k 2 ]
, and ppGq " 0 otherwise. Then, if k P t3, 4u, megpGq " l `k ´|V c |.

Otherwise (k ě 5), then

megpGq " $ ' ' & ' ' % 3, if |V c | " 0 l `2, if |V c | " 1 l `ppGq, if |V c | ą 1
Proof. Let G be a unicyclic graph where the only cycle C has length k and whose set of pendant vertices is LpGq. By Lemma 2.1, all leaves are part of any MEG-set of G. This implies that megpGq is at least l.

If |V C | " 0 (i.e. l " 0), we are done by Theorem 3.4, so let us assume |V C | ą 0 and thus, l ą 0. Similarly as in the proof of Lemma 2.3, for every vertex v of V C , we know that at least one leaf will exist in the tree component T v formed if we remove the neighbors of v in C from G. Informally speaking, towards the rest of the graph, this leaf simulates the fact that v is in the solution set.

If k P t3, 4u, we consider S " LpGq and we add to S all vertices of C that are of degree 2 in G. One can easily check that this is an MEG-set. Moreover, one can see that adding these degree 2 vertices is necessary by using similar arguments as in the proof of Theorem 3.4 on cycles.

Next, we assume that k ě 5. Let v 0 , . . . , v k´1 be the vertices of C.

When |V c | " 1, without loss of generality, consider the vertex in V c to be v 0 . Then, the vertices tv t k 3 u , v t 2k 3 u u on the cycle are sufficient to monitor the graph, in the same way as in Theorem 3.4. Moreover, by the same arguments as in the proof of Theorem 3.4, one can see that if at most one vertex on C is chosen in the MEG-set, some edge will not be monitored.

If |V c | ą 1 and ppGq " 0, the l pendant vertices are sufficient to monitor G. Indeed, consider an edge e. If e is not on C, let v be the vertex of V C closest to e, and let w ‰ v be the vertex of V C closest to v (it exists because |V c | ą 1). Consider a leaf f of G such that e lies on some path from v to f . Since ppGq " 0, the path from w to f is a unique shortest path, and thus, e is monitored by f and some leaf whose closest vertex on C is w.

If e is an edge of C, e lies on a path between two vertices v, w of V C . Since ppGq " 0, this path is a shortest path, and e is monitored by two leaves, each of which has v and w as its closest vertex of C, respectively.

Finally, consider the case where ppGq " 1 and |V c | ą 1. Since ppGq " 1, GrV pCqzV c s contains a path P whose length is at least

Y k 2
] and thus, the edges of P are not monitored by the set of leaves of G, which implies that megpGq ě l `1. To show that megpGq ď l `1, we select as an MEG-set, the set of leaves together with the middle vertex of P (if P has even length) or one of the middle vertices of P (if P has odd length). One can see that this is an MEG-set by similar arguments as in the previous case.

Complete graphs

The following follows immediately from Lemma 2.1, since every vertex of a complete graph is simplicial. Theorem 3.6. For any n ě 2, we have megpK n q " n.

Complete multipartite graphs

The complete k-partite graph K p1,p2,...,p k consists of k disjoint sets of vertices of sizes p 1 , p 2 , . . . , p k , with an edge between any two vertices from distinct sets. Theorem 3.7. We have megpK p1,p2,...,p k q " V pK p1,p2,...,p k q , with the exceptional case of a bipartite graph K 1,p with an independent set of size 1 (a star graph), for which megpK 1,p q " p.

Proof. In a complete k-partite graph, all vertices in a given partite set are twins. Therefore, by Lemma 2.2, all vertices of ant partite set of size at least 2 need to be a part of any MEG-set.

If we have several partite sets of size 1, then the vertices from these sets are closed twins, and again by Lemma 2.2 they all belong to any MEG-set.

Thus, we are done, unless there is a unique partite set of size 1, whose vertex we call v. If there are at least three partite sets, then note that v is never part of a unique shortest path, and thus the edges incident with v cannot be monitored if v is not part of the MEG-set.

On the other hand, if the graph is bipartite, it is a star K 1,p . Here, we know by Theorem 3.1 that megpGq " p, as claimed.

Hypercubes

The hypercube of dimension n, denoted by Q n , is the undirected graph consisting of k " 2 n vertices labeled from 0 to 2 n ´1 and such that there is an edge between any two vertices if and only if the binary representations of their labels differ by exactly one bit [START_REF] Saad | Topological properties of hypercubes[END_REF]. The Hamming distance HpA, Bq between two vertices A, B of a hypercube is the number of bits where the two binary representations of its vertices differ.

We next show that not only C 4 has the whole vertex set as its only MEG-set (Theorem 3.4), but that this also holds for all hypercubes.

Theorem 3.8. For a hypercube graph Q n with n ě 2, we have megpQ n q " 2 n .

Proof. Assume by contradiction that there is an MEG-set M of size at most 2 n ´1. Let v P V pGq be a vertex that is not in M . It is known that for every vertex pair tv x , vu with Hpv x , vq ď n, there are Hpv x , vq vertex-disjoint paths of length Hpv x , vq between them [START_REF] Saad | Topological properties of hypercubes[END_REF]. Thus, there is no vertex pair in M with a unique shortest path going through the edges incident with v, and M is not an MEG-set, a contradiction.

Grid graphs

The graph G Ü H is the Cartesian product of graphs G and H and with vertex set V pG Ü Hq " V pGqxV pHq, and for which tpx, uq, py, vqu is an edge if x " y and tu, vu P EpHq or tx, yu P EpGq and u " v. The grid graph Gpm, nq is the Cartesian product P m Ü P n with vertex set tpi, jq | 1 ď i ď m, 1 ď j ď nu. Theorem 3.9. For any m, n ě 2, we have megpGpm, nqq " 2pm `n ´2q.

Proof. We claim that the set S " tpi, jq P V pGpm, nqq i P t1, mu and 1 ď j ď n or j P t1, nu and 1 ď i ď mu of 2pm `n ´2q vertices of Gpm, nq that form the boundary vertices of the grid, form the only optimal MEG-set.

For the necessity side, let us assume that some vertex v " pi, jq of S is not part of the MEG-set. If v is a corner vertex (without loss of generality say v " p1, 1q, the two edges incident with v are not monitored, as for any shortest path going through them, there is another one going through vertex p2, 2q. If v is not a corner vertex (without loss of generality say v " p1, jq with 2 ď j ď n ´1), then the edge e between v " p1, jq and p2, jq is not monitored, indeed for any shortest path containing e, there is another one avoiding it, either going through vertex p2, j ´1q or through p2, j `1q.

To see that S is an MEG-set, first see that each boundary edge is monitored by its endpoints. Next, consider an edge e that is not a boundary edge, without loss of generality, e is between pi, jq and pi `1, jq. Then, it is monitored by p1, jq and pm, jq, whose unique shortest path goes through e.

Relation to feedback edge set number

A feedback edge set of a graph G is a set of edges which when removed from G leaves a forest. The smallest size of such a feedback edge set of G is denoted by fespGq and is sometimes called the cyclomatic number of G.

We next introduce the following terminology from [START_REF] Epstein | The (weighted) metric dimension of graphs : hard and easy cases[END_REF]. A vertex is a core vertex if it has degree at least 3. A path with all internal vertices of degree 2 and whose end-vertices are core vertices is called a core path. Do note that we allow the two end-vertices to be equal, but that every other vertex must be distinct. A core path that is a cycle (that is, both end-vertices are equal) is a core cycle. For the sake of distinction, a core path that is not a core cycle is called a proper core path. We say that a (non-empty) path from a core vertex u to a leaf v is a leg of u if all internal vertices of the path have degree 2 (u is not considered to be a part of the leg). The base graph of a graph G is the graph of minimum degree 2 obtained from G by iteratively removing vertices of degree 1. A hanging tree is a connected subtree of G which is the union of some legs removed from G during the process of creating the base graph G b of G. • One or two internal vertices from each proper core path belongs to M , only if the length is at least 2, as explained below.

• Two or three internal vertices from each core cycle, as explained below.

Consider a proper core path P , with core vertex endpoints c and c 1 , and the median vertex x 1 in the case of an odd-length path and x 1 , x 2 in the case of an even-length path, with d edges (on P ) between the endpoints and the respective medians in P . Then, we choose the single median vertex x 1 or the two median vertices x 1 , x 2 from each of the core paths into M .

For each core cycle, in addition to the core vertex of that cycle, we add three vertices that are as equidistant as possible on the cycle, to be part of M (as in Theorem 3.4).

Let e by any edge of G. We now show that our construction M monitors any such edge in G b . If e lies on a core cycle, assume an origin core vertex of v 0 . Then, based on Lemma 2.3 and Theorem 3.4, we deduce that in the worst case, four vertices together suffice to monitor the edges.

If the edge e lies on a proper core path P , then we have the following cases. Let c and c 1 be the core vertex endpoints of P , and the median vertex x 1 in the case of an odd-length path and x 1 , x 2 in the case of an even-length path and d edges of P between the end points and the respective medians in P . Without loss of generality, let us say that e lies on the path P such that its closest core vertex is c and closest median x 1 in the event of an even-length path. Suppose first that d is even. Given that the distance between c and x 1 is d in P , the length of any other path between them must be at least d `2. Therefore, c and x 1 monitor e. We can similarly argue that if the closest core vertex to e was c 1 and the closest median vertex was x 2 , then c 1 and x 2 monitor e. If e lay in between the median vertices x 1 and x 2 , then we know that those vertices would monitor e because they are adjacent. If the path was of odd length, then depending on which of the core vertices c and c 1 was closest to e, the distance between the median and the core vertices would be d in P and the length of any other path between them at least d `1, ensuring that the median vertex x 1 would monitor the edge apart from the core vertices. This justifies our construction of M for G b .

By Lemma 4.1, the number of core vertices of G b is at most 2k ´2, and there are at most 3k ´3 core paths.

If we have core cycles in our graph, then we must note that there can be at most k such cycles in the graph. Indeed, if there were k `1 core cycles in the graph, since they are all edge-disjoint, we need at least k `1 edges to be removed from G to obtain a forest, a contradiction to the fact that fespGq " k.

Let n c be the number of core cycles and n p be the number of proper core paths. We have |M | " 3n c `2n p `2k ´2. Since n c ď k and n c `np ď 3k ´3 by Lemma 4.1, we get|M | ď 3k `2p2k ´3q`2k ´2 " 9k ´8.

Recall that the max leaf number of G, denoted mlnpGq, is the maximum number of leaves in a spanning tree of G. It can be seen as a refinement of the feedback edge set number of G [START_REF] Eppstein | Metric dimension parameterized by max leaf number[END_REF]. We get the following corollary.

Corollary 4.4. For any graph G, we have megpGq ď 10 mlnpGq, where mlnpGq is the max leaf number of G.

Proof. It is known that fespGq ď mlnpGq [START_REF] Eppstein | Metric dimension parameterized by max leaf number[END_REF], and clearly, |LpGq| ď mlnpGq, thus the bound follows from Theorem 4.3. Proposition 4.5. For any integer k ě 2, there exists a graph G with fespGq " k and megpGq " 3k `|LpGq|.

Proof. Consider G and its base graph G b in Figure 3. We know that the leaves must be part of any MEG-set by Lemma 2.1. The MEG-set for G b consists of all the vertices in each of the core cycles (each a C 4 ) in G b , except the common core vertex. It is easy to check that no smaller set can work. The size of the optimal MEG-set in this example is 3k `|LpGq| and therefore, this is an instance where this proposition holds.

Conclusion

Inspired by a network monitoring application, we have defined the new concept of MEG-sets of a graph, which is a common refinement of the popular concept of a geodetic set and its variants, and of the previously studied distance-edge-monitoring sets.

We have studied the concept on basic graph classes. It is interesting to note that there are many graph classes which require the entire vertex set in any MEG-set: complete graphs, complete multipartite graphs, and hypercubes. It could thus be a difficult, but interesting, question, to characterize all such graphs.

Our upper bound using the feedback edge set number is probably not tight. What is a tight bound on this regard?

Finally, it remains to investigate computational aspects of the problem.

Figure 3 :

 3 Figure 3: Example of a graph G and its base graph G b with four core cycles.

  Two distinct vertices u and v of a graph G are open twins if N puq " N pvq and closed twins if N rus " N rvs. Further, u and v are twins in G if they are open twins or closed twins in G.

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

Acknowledgements

Florent Foucaud thanks Ralf Klasing and Tomasz Radzik for initial discussions which inspired the present study.

† Research financed by the French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25) and by the ANR project GRALMECO (ANR-21-CE48-0004-01).

Thus, G can be decomposed into its base graph and a set of maximal hanging trees. The root of such a maximal hanging tree T is the vertex common to T and G.

See Figure 2 for a graph whose core vertices are in red. It has two hanging trees, three core cycles, three proper core paths of length 4, and five proper core paths of length 1. Proof. Let G b be a base graph of G. Consider all vertices that are roots of maximal hanging trees on G b . By Theorem 3.1, the optimal MEG-set of each tree consists of all leaves. We repeatedly apply Lemma 2.3 to G, where for each application of Lemma 2.3, the cut-vertex is the root of a hanging tree in consideration. Lemma 2.1, Theorem 3.1 and Lemma 4.2 together imply that if fespGq " 0, then megpGq ď fespGq |LpGq|. Moreover, if fespGq " 1, then megpGq ď fespGq `|LpGq| `3, where |LpGq| is the number of leaves of G. We next give a similar bound when fespGq ě 2. Proof. Let k " fespGq. We show how to construct a MEG-set M of G b of order at most 9k ´8 and, by applying Lemma 4.2 to G, of order 9k ´8 `|LpGq| for G. If an edge e is part of a maximal hanging tree, then by Lemma 2.1 and Lemma 2.3, it is monitored by the leaves of G on the maximal hanging tree. M is constructed as follows.

• We let all core vertices of G b be part of M .