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 connected graph G_{a,b,c,d} for some specific parameters, (b) Section 3.2 provides modified constructions which prove the realizability of g(G)=2 and eg(G)=3 . (c) Section 3.3 extends the general realization for g(G)=2 and eg(G)\geq 4 , and (d) Section 3.4 generalizes the constructions to arbitrary parameter quadruples and analyze the computational complexity of our construction, showing that G_{a,b,c,d} can be built in O(d) time, with the number of vertices and edges growing linearly with the largest parameter d . (iii) Section 4 concludes the article with open directions for future research. 2 Preliminaries and known results Throughout this article, all graphs are finite, simple, and connected. For a graph G , we denote its vertex set by V(G) and its edge set by E(G) . A vertex v\in V(G) is simplicial if its neighborhood induces a clique in G , and it is called pendent if \deg_{G}(v)=1 . A vertex v is a cut vertex if the graph G\setminus\{v\} is disconnected. A clique of G is an induced subgraph that is a complete graph. Lemma 1 ( [ 3 ] ) . Let G be a graph with a cut-vertex u . Then u is never part of any minimal MEG-set of G . Lemma 2 ( [ 3 ] ) . In a connected 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 was shown in [ 3 ] that this implies that all pendant vertices of a graph G will be part of any geodetic set, edge-geodetic set, strong edge-geodetic set, and monitoring edge-geodetic set by lemma 2 . Two distinct vertices u,v are open twins if N(u)=N(v) , and closed twins if N[u]=N[v] . In this work, we simply refer to them as twins . Twins behave rigidly with respect to monitoring. Lemma 3 ( [ 3 ] ) . Every pair of (open or closed) twins of degree at least one belongs to every MEG-set. An important structural link between MEG-sets and strong edge-geodetic sets was established in [ 2 ] . Proposition 4 ( [ 2 ] ) . Let S\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 S . Then S is an MEG-set if and only if S , along with the assignment f , is a strong edge-geodetic set for any choice of f . Theorem 5 ( [ 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 for any vertex x\in N(v) , any induced 2-path uvx is part of a 4-cycle. Building on these structural observations, the next section first determines which parameter quadruples can occur in connected graphs, and then develops a refined construction that overcomes all remaining limitations. In particular, we show that every quadruple 2\leq a\leq b\leq c\leq d is realizable. 3 Main Results The structural observations collected in Section 2 impose strong restrictions on how the four parameters g(G) , eg(G) , seg(G) , and meg(G) may interact. Before presenting our constructions, we begin to use these constraints to eliminate several parameter quadruples that any connected graph cannot realize. These results form the first step toward a full characterization. 3.1 Eliminating impossible parameter quadruples We first identify certain parameter combinations that cannot be realized, clarifying structural limitations imposed by the preliminary results. Theorem 6 . For any integer d>2 , there does not exist a connected graph G satisfying g(G)=eg(G)=seg(G)=2\quad\text{and}\quad meg(G)=d. Proof. Assume, for the sake of contradiction, that such a connected graph G exists. Since g(G)=2 , there must exist a pair of vertices u,v such that every vertex of G lies on some shortest u\text{--}v path. Now, eg(G)=2 implies that every edge of G also lies on a shortest path between u and v . Since seg(G)=2 , there exists a set S=\{u,v\}\subseteq V(G) and an assignment that selects a particular shortest u\!-\!v path P_{uv} such that every edge of G lies on the chosen path P_{uv} . In other words, the set of edges of G is contained in the edge-set of P_{uv} ; hence every edge of G is an edge of P_{uv} . Consequently, there cannot exist any shortest u\!-\!v path different from P_{uv} : any alternative shortest path would use an edge not in P_{uv} , contradicting that all edges of G lie on P_{uv} . Thus P_{uv} is the unique shortest u\!-\!v path in G . As there is a unique shortest u - v path in G and this path covers all the vertices and edges of G , the graph G is precisely P_{uv} . Hence, meg(G)=meg(P_{uv})=2 , contradicting the assumption meg(G)=d>2 . This contradiction shows that no such graph G exists. ∎ We now exclude another set of parameter quadruples that are incompatible, specifically those with eg(G)=seg(G)=3 . Theorem 7 . There does not exist a connected graph G with parameters g(G)=2,\quad eg(G)=3,\quad seg(G)=3,\quad meg(G)=d\geq 3. In other words, G_{(2,3,3,d)} graphs do not exist. Proof. Since g(G)=2 , let \{u,v\} be a geodetic set of G . Then every vertex of G lies on some shortest u – v path. However, since eg(G)=3 , the pair \{u,v\} does not cover all edges. Therefore, there exists at least one edge xy\in E(G) which does not lie on any shortest u – v path. We observe that each of x and y appears on at least one shortest u – v path, but the edge xy never appears on any such path. Since eg(G)=3 and xy is not contained in any shortest u – v path, both x and y must be included in the edge-geodetic set to cover the edge xy . Due to this argument, x and y must be included in the strong edge-geodetic set as well. Since seg(G)=3 , let us say S=\{x,y,w\} which covers all edges. By definition of the strong edge-geodetic number, there exist specific shortest paths P_{xy},\quad P_{xw},\quad P_{yw} whose union covers all edges of G . This structure forces the union P_{xw}\cup P_{yw}\cup\{xy\} to contain at least one cycle. Note that there is no pendent vertex because every pandent vertex belongs to the intersection of all 4 parameters. Hence, u,v,x,y,w are not pendent vertices. In particular, the edge xy lies on P_{xy} , but P_{xy} does not intersect any shortest u – v path. At the same time, P_{xw} and P_{yw} must cover all remaining edges and pass through all vertices of the graph G . Due to the definition of a strong edge-geodetic set, there are unique shortest paths between x – w and y – w . Without loss of generality, let there be two shortest paths between x and w , then S cannot cover all edges of the graph G . Hence, there is a unique shortest path between x – w and y – w . Thus, G is the form as xy\cdots w\cdots x and it is a cycle in which every edge of the cycle must lie on some shortest u – v path. But the cycle contains the edge xy , which by assumption lies on no shortest u – v path. Therefore, it is a contradiction that no matter whether even or odd cycle, since g(G)\neq eg(G) . This is impossible. Therefore, no such graph G exists. ∎ Having identified the parameter quadruples with g(G)=2 and eg(G)=3 that cannot be realized, we now turn to the complementary task of establishing existence results. 3.2 Realizing the case g(G)=2 and eg(G)=3 In this subsection, we construct explicit families of connected graphs realizing all remaining admissible quadruples with g(G)=2\quad\text{and}\quad eg(G)=3, thereby completing the analysis for this parameter 2<30 . Finally, a vertex z is added and joined to w_{0} , u_{0} and w_{1} . In the case wherein d-c>0 is even, we add an additional twin v^{\prime}_{1{(r-1)}} to the vertex v_{1{(r-1)}} . We define the set V , Y and X as follows: V=\{v_{1{(r-1)}},\cdots,v_{(c-3){(r-1)}}\} , Y=\{v_{1r},\cdots,v_{(c-3)r}\} X\;=\;\begin{cases}\{v_{0i},v^{\prime}_{0i}:i=2n+1\text{ where }n\in\{0,\cdots,\frac{r-2}{2}\}\},&\text{if }d-c\text{ is odd},\\[2.84526pt] \{v_{0i},v^{\prime}_{0i}:i=2n+1\text{ where }n\in\{0,\cdots,\frac{r-2}{2}\}\}\cup\{v^{\prime}_{1{(r-1)}}\},&\text{if }d-c>0\text{ is even},\\[2.84526pt] \emptyset,&\text{if }d-c=0\end{cases} This is the construction of G_{2,3,c,d} where c\geq 4 . Now, we calculate the parameter g , eg , seg and meg of this construction graph as follows: Every vertex of G_{2,3,c,d} lies on at least one shortest path of either v_{0r} – x_{c-3} path or x_{0} – v_{(c-3)r} path. Hence, either \{v_{0r},x_{c-3}\} or \{x_{0} , v_{(c-3)r}\} is a geodetic set and g(G_{2,3,c,d})=2. Observe that the edge zw_{0} does not lie on any shortest either v_{0r} – x_{c-3} path or x_{0} – v_{(c-3)r} path. Therefore, it forces the vertex z must belong to every edge-geodetic set to cover all incident edges of z . Moreover, since no pair of vertices covers all edges of the graph, we take the set with at least 3 vertices. Let S_{eg}=\{z,x_{0},v_{(c-3)r}\}. We claim that S_{eg} is an edge-geodetic set. Indeed, the pair \{x_{0},v_{(c-3)r}\} covers all edges of the layered structure of the graph, while the pairs \{z,x_{0}\} and \{z,v_{(c-3)r}\} cover the edges incident with z . Hence, the edge-geodetic number of the graph is, eg(G_{2,3,c,d})=|S_{eg}|=3 Since z belongs to every edge-geodetic set, Lemma 8 implies that z belongs to every strong edge-geodetic set. Furthermore, the edges of the paths x_{0}w_{0}z , x_{0} – v_{0r} and the twin vertices on the z – v_{0r} paths force the inclusion of the vertices x_{0} and v_{0r} in the strong edge-geodetic set. For each i\in\{1,\dots,c-3\} , the edge v_{i{(r-1)}}v_{ir} lies on a unique shortest v_{i{(r-1)}} – v_{ir} path. Hence, at least one of v_{i{(r-1)}} or v_{ir} must belong to any strong edge-geodetic set when d-c is odd. When d-c is even, v_{ir} must belong to any strong edge-geodetic set to cover the v^{\prime}_{1(r-1)}v_{1r} . Consequently, every strong edge-geodetic set has cardinality at least c . On the other hand, the set \{x_{0},z,v_{0r}\}\cup\{v_{1r},\dots,v_{(c-3)r}\} admits a choice of shortest paths whose union covers all edges of G_{2,3,c,d} . Therefore, seg(G_{2,3,c,d})=|\{x_{0},z,v_{0r}\}|+|Y|=3+c-3=c. By Lemma 9 , the vertex z belongs to every monitoring edge-geodetic set. Moreover, for each i\in\{1,\dots,c-3\} , at least one of v_{i{(r-1)}} or v_{ir} must belong to every monitoring edge-geodetic set. However, choosing v_{ir} does not allow all edges to be monitored, whereas the vertices v_{i{(r-1)}} , together with x_{0} , z and vertices of X (as they are twins and by the lemma 3 ), monitor all edges of the graph. Thus, the set \{x_{0},z\}\cup\{v_{1(r-1)},\dots,v_{(c-3)(r-1)}\}\cup X is a monitoring edge-geodetic set, and no smaller such set exists. Hence, meg(G_{2,3,c,d})=\begin{cases}|\{x_{0},z\}|+|V|+|X|=2+c-3+d-c+1=d,&\text{if }d-c>0,\\[2.84526pt] |\{x_{0},z,v_{00}\}|+|V|+|X|=3+c-3+0=c=d,&\text{if }d-c=0\\[2.84526pt] \end{cases} This completes the proof. ∎ 3.3 General realization for g(G)=2 and eg(G)\neq 3 The previous Section 3.1 and section 3.2 were devoted to the detailed analysis of the case g(G)=2 and eg(G)=3 , including both non-existence results and explicit constructions realizing all admissible parameter quadruples. We now move beyond this exceptional case and establish a general existence theorem for all remaining admissible quadruples with g(G)=2 . Theorem 12 . For any positive integers 2=a\leq b\leq c\leq d , except for b=3 , there exists a connected graph G_{2,b,c,d} with g(G_{2,b,c,d})=2,\quad eg(G_{2,b,c,d})=b,\quad seg(G_{2,b,c,d})=c,\quad meg(G_{2,b,c,d})=d. Proof. y x_{0} z_{1} w_{1} z_{2} w_{2} z_{b-2} w_{b-2} f_{1} v_{1} f_{2} v_{2} f_{c-b+1} v_{c-b+1} (a) 2,b,c,d where b\neq 3 and d-c=0 . y x_{0} z_{1} w_{1} z_{2} w_{2} z_{b-2} w_{b-2} f_{1} v_{1} f_{2} v_{2} f_{c-b+1} v_{c-b+1} x_{1} x_{2} x_{3} x_{4} x_{5} x_{r-2} x_{r-1} x_{r} x^{\prime}_{2} x^{\prime}_{4} x^{\prime}_{r-1} (b) 2,b,c,d where b\neq 3 and d-c is odd. y x_{0} z_{1} w_{1} z_{2} w_{2} z_{b-2} w_{b-2} f_{1} v_{1} f_{2} v_{2} f_{c-b+1} v_{c-b+1} x_{1} x_{2} x_{3} x_{4} x_{5} x_{r-3} x_{r-2} x_{r-1} x_{r} x^{\prime}_{2} x^{\prime}_{4} x^{\prime}_{r-2} x^{\prime}_{r-1} (c) 2,b,c,d where b\neq 3 , d-c>0 and d-c is even. We construct G_{2,b,c,d} except for b=3 in three cases depending on the parity of d-c . Define r=\begin{cases}d-c,&d-c\text{ odd},\\[5.69054pt] d-c+2,&d-c>0\text{ even},\\[5.69054pt] 0,&d-c=0.\end{cases} At the beginning, drawing a path P_{r+4} and labeling the vertices in order as y , z_{1} , w_{1} , x_{0} , x_{1},\dots,x_{r} . Then, we add b-3 parallel paths yz_{i}w_{i}x_{0} from y to x_{0} where i\in\{2,\dots,b-2\} . Let W=\{w_{1},\dots,w_{\,b-2}\}, and make W a clique. Next again, adding c-b+1 additional parallel paths yf_{i}v_{i}x_{0} from y to x_{0} where i\in\{1,2,\dots,c-b+1\} . For each i\in\{1,\dots,c-b+1\} , let V=\{v_{1},\dots,v_{c-b+1}\}. For the last step of the construction, We distinguish the three cases: (i) If d-c>0 even , we add open twins x^{\prime}_{2i} to each vertex x_{2i} , 1\leq i\leq\lfloor\frac{d-c-1}{2}\rfloor , and add a parallel path x_{r-3}x^{\prime}_{r-2}x^{\prime}_{r-1}x_{r} . Define X=\{x_{2i},x^{\prime}_{2i}:1\leq i\leq\big\lfloor\frac{d-c-1}{2}\big\rfloor\}\cup\{x_{r-1},x^{\prime}_{r-1}\}. (ii) If d-c odd , add open twins x^{\prime}_{2i} to each x_{2i} for 1\leq i\leq\lfloor\frac{d-c}{2}\rfloor . Set X=\{x_{2i},x^{\prime}_{2i}:1\leq i\leq\lfloor\frac{d-c}{2}\rfloor\}\cup\{x_{r}\}. (iii) If d-c=0 , set X=\emptyset . This completes the construction. Now, we present the calculation of g , eg , seg , and meg is as follows: Every vertex of the graph G_{2,b,c,d} is covered in at least one of the shortest paths between vertices y and x_{r} . Hence, the geodetic set is \{y,x_{r}\} and the geodetic number is g(G_{2,2,c,d})=|\{y,x_{r}\}|=2 Observe that none of the shortest paths between y and x_{0} covers the edges of the clique W . Thus, w_{i}\in W must be chosen as in our edge-geodetic set. Hence, edge-geodetic set is \{y,x_{0}\}\cup W and the edge-geodetic number of the graph is eg(G_{2,b,c,d})=|\{y,x_{0}\}|+|W|=2+(b-2)=b. For the strong edge-geodetic set, we notice that the path yz_{1}w_{1}x_{0}x_{1}\cdots x_{r} in the graph G_{2,b,c,d} is a diametral path. Hence, need to include y and x_{r} as they are the terminal vertices on the opposite ends of the graph and all the vertices of W to cover the edges of the clique. Hence, we can assign that a shortest y – x_{r} path can cover at most one of the c-b+1 parallel paths yf_{i}v_{i}x_{0} . Without loss of generality, assume it covers yf_{1}v_{1}x_{0} . Thus, to cover the remaining yf_{i}v_{i}x_{0} paths, all remaining v_{i} (for i\geq 2 ) must be included. Hence, the strong edge-geodetic set is \{y,x_{r}\}\cup W\cup(V\setminus\{v_{1}\}) and strong edge-geodetic number is seg(G_{2,b,c,d})=|\{y,x_{r}\}|+|W|+(|V|-1)=2+b-2+c-b+1-1=c For the calculation of the monitoring edge-geodetic number, we know that all edges of the clique require all w_{i} in W . Then, to monitor all edges that lie on the shortest paths between y and w_{i} , y is required to add to the MEG-set. Moreover, to monitor all parallel edges between y and x_{0} , each v_{i} is required to monitor those parallel paths. Furthermore, we know that all twin vertices must be included in the MEG-set. In this case, we proceed with three cases separately as per the values of r , (i) When d-c>0 even , we need to take twin vertices along with the vertices x_{r-1} and x^{\prime}_{r-1} to monitor edges of the C_{6} formed on the end of the path x_{0}x_{1}\dots x_{r} . Hence, the MEG-set of G_{2,b,c,d} is \{y\}\cup W\cup V\cup X and meg(G_{2,b,c,d})=|\{y\}|+|W|+|V|+|X|=1+b-2+c-b+1+2(\frac{d-c-2}{2})+2=d (ii) When d-c is odd, we need to take twin vertices along with vertex x_{r} to monitor all final edges x^{\prime}_{r-1}x_{r} and x_{r-1}x_{r} . Hence, the MEG-set of G_{2,b,c,d} is \{y\}\cup W\cup V\cup X and meg(G_{2,b,c,d})=|\{y\}|+|W|+|V|+|X|=1+b-2+c-b+1+2\frac{(d-c-1)}{2}+1=d (iii) When d-c=0 , there does not exist any twin vertices and X=\emptyset . Hence, y to each w_{i} and each w_{i}x_{0} to each x_{0}v_{i} and the edges of the clique in W have been monitored by \{y\}\cup W\cup V . Hence, the vertex x_{0} is not required to take as in the MEG-set. Hence, the monitoring edge-geodetic number of the graph is, meg(G_{2,b,c,d})=|\{y\}|+|W|+|V|=1+b-2+c-b+1=c=d Thus in all cases, meg(G_{2,b,c,d})=d , completing the proof. ∎ While Theorem 12 guarantees the existence of graphs realizing all admissible parameter quadruples with g(G)=2 and eg(G)\neq 3 , its proof relies on several case-dependent arguments. We now present a general construction framework that subsumes these cases and systematically produces graphs with prescribed values of the four parameters. 3.4 Generalizing the construction to arbitrary parameters So far, our analysis has focused on graphs with geodetic number g(G)=2 . Using the general construction framework introduced in Section 3.4 , we now extend these results to arbitrary values of the geodetic number. In particular, we show that every admissible parameter quadruple (a,b,c,d) with 3\leq a\leq b\leq c\leq d can be realized by a connected graph. Theorem 13 . For any integers 3\leq a\leq b\leq c\leq d , there exists a connected graph G_{a,b,c,d} satisfying g(G_{a,b,c,d})=a,\qquad eg(G_{a,b,c,d})=b,\qquad seg(G_{a,b,c,d})=c,\qquad meg(G_{a,b,c,d})=d. Proof. y w_{1} z v_{1} x w_{2} w_{3} w_{b-a+1} w_{b-a+2} u_{1} u_{2} u_{3} u_{a-3} v_{2} v_{3} v_{4} x_{1} x_{2} x_{3} x_{4} x_{5} x_{r-3} x_{r-2} x_{r-1} x_{r} x^{\prime}_{r-2} x^{\prime}_{r-1} x^{\prime}_{2} x^{\prime}_{4} Figure 3 : G_{a,b,c,d} showing the clique W and extension V when d-c is odd. y w_{1} z v_{1} x w_{2} w_{3} w_{b-a+1} w_{b-a+2} u_{1} u_{2} u_{3} u_{a-3} v_{2} v_{3} v_{4} x_{1} x_{2} x_{3} x_{4} x_{5} x_{r-2} x_{r-1} x_{r} x^{\prime}_{r-1} x^{\prime}_{2} x^{\prime}_{4} Figure 4 : G_{a,b,c,d} showing the clique W and extension V when d-c is even. We present a unified construction of G_{a,b,c,d} that achieves the desired parameter values. Begin the construction with a 5-cycle whose label of vertices (in counterclockwise order) x,\,y,\,w_{1},\,z,\,v_{1},\,x. Next, we add either |W|=b-a or |W^{\prime}|=b-a+1 new vertices as either W=\{w_{2},w_{3},\dots,w_{b-a+1}\},\ or\ \ W^{\prime}=\{w_{2},w_{3},\dots,w_{b-a+2}\} and make either W\cup\{w_{1}\} or W^{\prime}\cup\{w_{1}\} into a clique (if b=a then W=\varnothing and no clique edges are added). Place these clique vertices in the figure between y and z so that each w_{i} is adjacent to both y and z . In this step, if a=3 , then we add W and otherwise, we add W^{\prime} . In the third step of construction, add |V|=c-b vertices V=\{v_{2},\dots,v_{c-b+1}\}. and for each v_{i}\in V insert the two edges zv_{i} and v_{i}x . In the next step, add |U|=a-3 pendent vertices U=\{u_{1},u_{2},\dots,u_{a-3}\}, and attach them all to the vertex either w_{b-a+1} in W or w_{b-a+2} in W^{\prime} (if a=3 then there is no pendent vertex in the construction graph). Now, we add one more pendent vertex x_{r} attached to the vertex x as an xx_{r} edge. In the last step of construction, we subdivide the xx_{r} edges by adding r-1 vertices x_{1},x_{2},\cdots,x_{r-1} where r\;=\;\begin{cases}d-c+3,&\text{if }d-c\text{ is odd},\\[2.84526pt] d-c+1,&\text{if }d-c\text{ is even},\end{cases} and then add the open twin vertices x^{\prime}_{2i} on each x_{2i} as follows: If (d-c) is odd, the twin vertices x^{\prime}_{2i} for i=\{1,2,\cdots,\lfloor\frac{(r-3)}{2}\rfloor\} , let X=\{x_{2i},x^{\prime}_{2i}:1\leq i\leq\lfloor\frac{(r-3)}{2}\rfloor\}\cup\{x_{r-1},x^{\prime}_{r-1}\}, and add the parallel path from x_{r-3} to x_{r} with distance 3 , then we can see it as a 6 cycle form with the labeled x_{r-3},x_{r-2},x_{r-1},x_{r},x^{\prime}_{r-1},x^{\prime}_{r-2},x_{r-3} . If (d-c) is even, then x^{\prime}_{2i} for i=\{1,2,\cdots,\lfloor\frac{(r-1)}{2}\rfloor\} , let X^{\prime}=\{x_{2i},x^{\prime}_{2i}:1\leq i\leq\lfloor\frac{r-1}{2}\rfloor\}\cup\{x_{r}\}, In this case, we note that if d-c=0 , then X^{\prime}=\emptyset and r=1 . This completes the construction of the graph G_{a,b,c,d} . After establishing this construction completely, we now verify the four parameters one by one. First, we verify the geodetic number by considering separately the cases a=3 and a\geq 4 . If a=3 , there are no pendent vertices on the w_{b-a+1} . Define S_{g}\;:=\;\{y,\,z,\,x_{r}\}. We claim that S_{g} is a geodetic set of size 3 . Since every vertex w_{i} is adjacent to both y and z , hence each w_{i} lies on every shortest path between y and z . By construction, the shortest paths z\!-\!x_{r} and y\!-\!x_{r} together cover all vertices and edges along the branches from x to x_{r} . Moreover, every vertex v_{j} with 1\leq j\leq c-b+1 is adjacent to both z and x , so each v_{j} lies on a shortest path between z and x_{r} . Consequently, every vertex of G_{3,b,c,d} is contained in some shortest path between any two vertices of S_{g} , implying g(G_{3,b,c,d})\leq 3 . Since no nontrivial connected graph satisfies g(G)=1 , and any two vertices, such as w_{i} and x_{r} fail to cover all vertices through their shortest paths in G_{3,b,c,d} , it follows that g(G_{3,b,c,d})\geq 3 . Combining this with the upper bound established above, we obtain g(G_{3,b,c,d})=3 . If a\geq 4 , the construction introduces the pendent vertices U=\{u_{1},u_{2},\ldots,u_{a-3}\} are attached to w_{b-a+2} . Let S^{\prime}_{g}:=\{y,\,z,\,x_{r}\}\cup U. Due to Lemma 2 , U must belong to all four parameter sets. Hence, each u_{i} lies on a unique shortest paths ending at w_{b}-a+2 which itself lies on the shortest path between y and z . As before, the paths y\text{--}x_{r} and z\text{--}x_{r} cover all vertices between x and x_{r} . Removing any vertex from S^{\prime}_{g} leaves at least one pendent vertex or internal vertex uncovered, so S^{\prime}_{g} is minimal. Hence, g(G_{a,b,c,d})=|S^{\prime}_{g}|=3+a-3=a. From the preceding arguments, all pendent vertices U and the terminal vertex x_{r} must belong to every edge-geodetic set. Every shortest path between each pendent vertices and x_{r} includes the edges of the paths u_{i}w_{b-a+2}yx\cdots x_{r} , thus covering all edges along the branches from y and x to x_{r} . However, these vertices alone do not cover the edges internal to the clique W or those forming as yw_{i}zv_{j}x for 1\leq i\leq b-a+1 . Therefore, the vertices w_{i} ( 1\leq i\leq b-a+1 ) must also belong to every edge-geodetic set. Additionally, since z is required to cover the edges incident to each v_{j} , we must include z as well. Consequently, the edge-geodetic set of G_{a,b,c,d} can be taken as S_{eg}=U\cup(W\setminus\{w_{b-a+2}\})\cup\{w_{1},z,x_{r}\}, Hence, eg(G_{a,b,c,d})=|S_{eg}|=(a-3)+(b-a)+3=b. If a=3 , there are no pendent vertices and then w_{i} with 1\leq i\leq b-a+1 must belong to the edge-geodetic set. Therefore the edge-geodetic set reduces to S^{\prime}_{eg}=(W\cup\{w_{1}\})\cup\{z,x_{r}\}, which again satisfies eg(G_{3,b,c,d})=|S^{\prime}_{eg}|=(b-a)+1+2=b. We now determine the strong edge-geodetic number of G_{a,b,c,d} . Let S_{seg} be a strong edge-geodetic set of G_{a,b,c,d} . As established in our construction, we note that all vertices of the clique W\cup\{w_{1}\} must belong to any strong edge-geodetic set to cover the edges of W\cup\{w_{1}\} when a=3 . Indeed, to monitor the edges in U\cup W^{\prime}\cup\{w_{1}\} when a\geq 4 , U\cup(W^{\prime}\setminus\{w_{b-a+2}\})\cup\{w_{1}\} must belong to any strong edge-geodetic set S_{seg} . Together with U\cup\{x_{r}\} , these vertices cover all pendent branches and the edges incident to the clique. However, each edges incident to vertices in V=\{v_{1},\dots,v_{c-b+1}\} adjacent to both z and x are not yet covered by above vertices even though the vertex z is including in S_{seg} that can cover one vertex, say v_{1} between z and x . Hence, to ensure coverage, we must include all vertices of V . Hence, the strong edge-geodetic set of G_{a,b,c,d} is: If a=3 , \displaystyle S_{seg}=(W\cup\{w_{1}\})\cup\{z,x_{r}\}\cup V, and the strong edge-geodetic number is seg(G_{3,b,c,d})=|S_{seg}|=|W|+|\{w_{1},z,x_{r}\}|+|V|=b-a+3+c-b=c. Otherwise, S_{seg}=U\cup(W^{\prime}\setminus\{w_{b-a+2}\})\cup\{x_{r}\}\cup V, and the strong edge-geodetic number is \displaystyle seg(G_{a\geq 4,b,c,d}) \displaystyle=|S_{seg}|=|U|+|(W^{\prime}\setminus\{w_{b-a+2}\}|+|\{w_{1},z,x_{r}\}|+|V| \displaystyle=a-3+b-a+3+c-b=c. Therefore, seg(G_{a,b,c,d})=c. Finally, we determine the monitoring edge-geodetic number of G_{a,b,c,d} . From the construction and by Lemma 2 , all pendent vertices in U must belong to any MEG-set. Then, to monitor all edges of the clique W , the vertices of the clique either W\cup\{w_{1}\} or (W^{\prime}\setminus\{w_{b-a+2}\})\cup\{w_{1}\} must belong to any MEG-set (Note that w_{b-a+2} is a cut vertex) . Since each vertex v_{i} of V\cup\{v_{1}\} is an induced 2 -path zv_{i}x form which is a part of C_{4} , v_{i} must belong to MEG-set by Theorem 5 . Moreover, by Lemma 3 , every pair of open twins in either X\setminus\{x_{r-1},x^{\prime}_{r-1}\} or X^{\prime}\setminus\{x_{r}\} must also be contained in every MEG-set. Now, we verify for the remaining edges by considering the following: If d-c is even, we have r=d-c+1 . Since X^{\prime}\setminus\{x_{r}\} belongs to every MEG-set, x_{r-1} and x^{\prime}_{r-1} are also belong to the every MEG-set of G_{a,b,c,d} . However, x_{r-1}x_{r} and x^{\prime}_{r-1}x_{r} edges still remain to be monitored. Since x^{\prime}_{r-1}x_{r}x_{r-1} is an induced 2 -path and it is a part of C_{4} , x_{r} must be inculded in every MEG-set due to Theorem 5 . Hence, the MEG-set of G_{a,b,c,d} for d-c=even is either (W\cup\{w_{1}\})\cup(V\cup\{v_{1}\})\cup X^{\prime}\ \ \ \ \ \ or\ \ \ \ \ \ \ U\cup(W\cup\{w_{1}\})\cup(V\cup\{v_{1}\})\cup X^{\prime} where |X^{\prime}|=2\frac{r-1}{2}+1=2\frac{d-c}{2}+1. \displaystyle meg(G_{3,b,c,d}) \displaystyle=|(W\cup\{w_{1}\})|+(V\cup\{v_{1}\})|+|X^{\prime}| \displaystyle=(b-3+1)+(c-b+1)+2\ \frac{d-c}{2}+1=d\ \ and \displaystyle meg(G_{a\geq 4,b,c,d}) \displaystyle=|U|+|(W^{\prime}\setminus w_{b-a+2})\cup\{w_{1}\}|+(V\cup\{v_{1}\})|+|X^{\prime}| \displaystyle=(a-3)+(b-a+1)+(c-b+1)+2\frac{d-c}{2}+1=d. If d-c is odd, we have r=d-c+3 . Since X\setminus\{x_{r-1},x^{\prime}_{r-1}\} belong to every MEG-set, x_{r-4} and x^{\prime}_{r-4} are also belong to the every MEG-set of G_{a,b,c,d} . However, the edges x_{r-4}x_{r-3} , x_{r-3}x^{\prime}_{r-4} and the path x_{r-3}x_{r-2}x_{r-1}x_{r}x^{\prime}_{r-1}x^{\prime}_{r-2}x_{r-3} in C_{6} form are not monitored yet. As per construction, if we add only one vertex of C_{6} form, it cannot monitor some edges. Hence, we note that the vertices x_{r-1} and x^{\prime}_{r-1} must be in the MEG-set of G_{a,b,c,d} . Then, all remaining edges will be covered. Therefore, x_{r-1} and x^{\prime}_{r-1} must be in the MEG-set of G_{a,b,c,d} . Hence, the MEG-set G_{a,b,c,d} for d-c=odd is either (W\cup\{w_{1}\})\cup(V\cup\{v_{1}\})\cup X\ \ \ \ \ \ or\ \ \ \ \ \ \ U\cup(W^{\prime}\cup\{w_{1}\})\cup(V\cup\{v_{1}\})\cup X where |X|=2\ \frac{r-4}{2}+2=2\ \frac{d-c-1}{2}+2. \displaystyle meg(G_{3,b,c,d}) \displaystyle=|(W\cup\{w_{1}\})|+(V\cup\{v_{1}\})|+|X| \displaystyle=(b-3+1)+(c-b+1)+(d-c+1)=d\ \ and \displaystyle meg(G_{a\geq 4,b,c,d}) \displaystyle=|U|+|(W^{\prime}\setminus w_{b-a+2})\cup\{w_{1}\}|+(V\cup\{v_{1}\})|+|X| \displaystyle=(a-3)+(b-a+1)+(c-b+1)+(d-c+1)=d. This completes the proof. ∎ Having established the existence of graphs realizing arbitrary admissible parameter quadruples and described an explicit construction for G_{a,b,c,d} , we now briefly analyze the size and computational complexity of the construction. 3.4.1 Complexity of the construction Let G_{a,b,c,d} be the graph constructed in Theorem 13 . The number of vertices and edges in G_{a,b,c,d} grows linearly with d . Starting from the base graph realizing g(G)=a , we introduce three types of gadgets: eg-gadget , seg-gadget , and meg-gadget , each of which contributes a constant number of vertices and edges per increment of the corresponding parameter. The necessary gadgets can be attached sequentially to achieve the desired parameters (b,c,d) . Since adding each gadget requires O(1) operations and at most d gadgets are needed, the overall construction can be completed in O(d) steps. Therefore, the total size of the graph satisfies |V(G_{a,b,c,d})|=O(d) and which we summarize in the following corollary. Corollary 14 . Given integers a\leq b\leq c\leq d , a graph G_{a,b,c,d} realizing (g,eg,seg,meg)=(a,b,c,d) can be constructed on O(d) . Proof. The construction of G_{a,b,c,d} starts from a fixed base graph realizing g(G)=a . To achieve the target values of eg(G)=b , seg(G)=c , and meg(G)=d , we sequentially attach a collection of gadgets, each of which increases exactly one of the parameters by 1 while preserving the previously achieved values. Each gadget consists of a constant number of vertices and edges and can be attached to the existing graph using a constant number of operations. Since at most d gadgets are required to reach the largest parameter meg(G)=d , the total number of construction steps is O(d) and the entire construction can be performed on O(d) . ∎ 4 Conclusion In this article, we have conducted a systematic study of connected graphs with prescribed values of four related parameters: 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) . We first identified combinations of parameters that are impossible to realize, providing a series of non-existence results for certain parameter quadruples. Next, for all admissible quadruples (a,b,c,d) , we presented explicit constructions of connected graphs G_{a,b,c,d} realizing these parameters. Our constructions are flexible and modular, allowing us to generate graphs for arbitrary parameter values while maintaining linear size and ensuring efficient construction. Moreover, we analyzed the computational complexity of our construction, demonstrating that G_{a,b,c,d} can be built in O(d) steps, with the number of vertices and edges growing linearly with the largest parameter d . This shows that our approach is not only constructive but also practical for generating large graphs with desired properties. These results complete the characterization of realizable parameter quadruples and provide a foundation for further investigations. Future work may include studying additional network parameters, exploring extremal properties related to graph size and diameter, or extending the analysis to weighted or directed graphs. Data availability This work has no associated data. Declaration Conflict of interest The authors have no competing interests.