On four network monitoring parameters in graphs and their gaps
Zin Mar Myint, Avikal Srivastava · 2026
Read On four network monitoring parameters in graphs and their gaps by Zin Mar Myint, Avikal Srivastava (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-27696.txt.
Introduction
Myint and Srivastava probe gaps among four network monitoring numbers. Each number counts the fewest nodes needed to watch a graph. Rules grow stricter across the four variants. A known chain orders them from small to large. A 2025 question asked if any ordered values can occur. Past work settled only special cases. This study finds quadruples no connected graph can realize. New constructions cover other value ranges.
Catalog record
| CREATOR | Zin Mar Myint, Avikal Srivastava |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41818 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.27696
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On four network monitoring parameters in graphs and their gaps Zin Mar Myint, Avikal Srivastava Abstract Let G G be a finite simple undirected graph. Four graph parameters related to network monitoring are the geodetic set , edge geodetic set , strong edge geodetic set , and monitoring edge geodetic set , with corresponding minimum sizes, denoted by g ( G ) , e g ( G ) , s e g ( G ) g(G),eg(G),seg(G) , and m e g ( G ) meg(G) , respectively. These parameters quantify the minimum number of vertices required to monitor all vertices and edges of G G under progressively stricter path-based conditions. As established by Florent et al. (CALDAM 2023), these parameters satisfy the chain of inequalities: g ( G ) ≤ e g ( G ) ≤ s e g ( G ) ≤ m e g ( G ) . g(G)\leq eg(G)\leq seg(G)\leq meg(G). In 2025, Florent et al. posed the following question: given integers a , b , c , d a,b,c,d satisfying 2 ≤ a ≤ b ≤ c ≤ d 2\leq a\leq b\leq c\leq d , does there exist a graph G G such that g ( G ) = a , e g ( G ) = b , s e g ( G ) = c , and m e g ( G ) = d ? g(G)=a,\quad eg(G)=b,\quad seg(G)=c,\quad\text{and}\quad meg(G)=d? They partially answered this affirmatively under three specific hypotheses and gave some constructions to support it. In this article, we first identify quadruples of values that cannot be realized by any connected graph. For all remaining admissible quadruples, we provide explicit constructions of connected graphs that realize the specified parameters. These constructions are modular and efficient, with the number of vertices and edges growing linearly with the largest parameter, providing a complete and constructive characterization of such realizable quadruples. Keywords: Network monitoring, Geodetic set, Edge-geodetic set, Strong edge-geodetic set, Monitoring edge-geodetic set. 1 Introduction Distance-based monitoring through graph theoretic models provide a fundamental framework for network path observability, fault detection and routing verification in network problems. A key minimization problem in this area is to determine the minimal subset of strategically selected vertices such that they reveal the structure of shortest paths in the graph. To capture different levels of monitoring or fault-detection capability, several vertex-based parameters have been introduced, each imposing progressively stronger requirements on how vertices or edges are covered by a selected collection of "probes" whose shortest path interactions expose structural information or detect faults in the network. There are four parameters relevant to the context of this article, namely, the geodetic number g(G) , the edge-geodetic number eg(G) , the strong edge-geodetic number seg(G) , and the monitoring edge-geodetic number meg(G) . They play central roles in measuring the efficiency of probe placement in communication networks. A set S\subseteq V(G) is called a geodetic set if every vertex x\in V(G) lies on any shortest path between some pair of distinct vertices in S . The minimum cardinality of a geodetic set is the geodetic number of G , denoted by g(G) . This concept was first introduced by Harary et al. [ 4 ] . An edge-geodetic set of a graph G is a vertex subset S\subseteq V(G) such that every edge of G lies on any shortest path between some pair of distinct vertices in S . The minimum cardinality of an edge-geodetic set is the edge-geodetic number of G , denoted by eg(G) , a notion introduced by Atici et al. [ 1 ] . Later, Manuel et al. [ 5 ] refined this notion further by defining the strong edge-geodetic set, which states that, instead of allowing all shortest paths between each pair of selected vertices, one must designate a specific shortest path for each pair, and the union of these chosen paths must cover all edges of the graph. Hence, a strong edge-geodetic set of the graph G is a vertex subset S\subseteq V(G) together with a choice of a specific shortest path P_{uv} for each unordered pair of distinct vertices u,v\in S , such that every edge of G lies on at least one of these chosen paths. The minimum cardinality of such a set is the strong edge-geodetic number , denoted seg(G) . The most recent and most restrictive parameter in this family is the monitoring edge-geodetic set (MEG-set), introduced by Foucaud et al. [ 3 ] in the context of fault detection. Here, the requirement is that every edge must be monitored by some pair of vertices in S\subseteq V(G) where a pair u,v\in S monitors an edge e if e lies on every shortest u – v path in G . The minimum cardinality of such a set is the monitoring edge-geodetic number of G , denoted meg(G) . These four parameters are known [ 2 ] to hold the following relation g(G)\leq eg(G)\leq seg(G)\leq meg(G), and each corresponds to increasingly stringent monitoring conditions capturing a progressively stronger notion of coverage. Moreover, the relationships among these four g(G),eg(G),seg(G) , and meg(G) were analyzed in detail in Foucaud et al. [ 2 ] , where the authors initiated a systematic study of the possible differences between them. A central problem posed in that work is the following: In [ 2 ] , given integers 2\leq a\leq b\leq c\leq d , does there exist a connected graph G such that g(G)=a,\ eg(G)=b,\ seg(G)=c,\ meg(G)=d\,? In the same paper, the authors constructed graphs showing that nearly all quadruples 4\leq a\leq b\leq c\leq d are realizable, subject to a small number of exceptional configurations. Their constructions rely on bipartite base graphs with pendent attachments and carefully arranged subdivisions, using interactions among simplicial vertices, creating the clique and twin structures to control the parameter values. However, some specific cases, particularly those involving smaller values or tight equalities between consecutive parameters (for instance, when d=c+1 with b=a+1 ), were excluded by the constraints of the original construction. Moreover, the structural behavior of the resulting graphs suggests that further refinement and generalization of the construction might bridge these exceptional gaps and lead to a complete characterization for all positive integers 2\leq a\leq b\leq c\leq d . 1.1 Our contributions In this article, we resolve the realizability problem completely. We introduce a modified and structurally flexible construction that produces, for every integer quadruple 2\leq a\leq b\leq c\leq d, a connected graph G satisfying g(G)=a , eg(G)=b , seg(G)=c , and meg(G)=d . Our approach refines the building of construction that was used in [ 2 ] , allowing for precise control over the roles of simplicial vertices, twins, pendant attachments, and subdivided paths, and eliminating all previously unresolved cases. This establishes the first complete description of the achievable combinations of the four monitoring-related parameters. (i) Section 2 recalls the corresponding definitions and known results that will be used throughout the article, including structural lemmas for vertices that must belong to every monitoring edge-geodetic set. (ii) Section 3 is divided into four parts: (a) Section 3.1 shows that there does not exist any