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

Florent Foucaud (1) , Pierre-Marie Marcille (2) , Zin Mar Myint (3) , R B Sandeep (3) , Sagnik Sen (3) , S Taruni (3)

1 LIMOS - Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes
2 LaBRI - Laboratoire Bordelais de Recherche en Informatique
3 IITD - IIT Dharwad

A monitoring edge-geodetic set, or simply an MEG-set, of a graph $G$ is a vertex subset $M \subseteq V(G)$ such that given any edge $e$ of $G$, $e$ lies on every shortest $u$-$v$ path of $G$, for some $u,v \in M$. The monitoring edge-geodetic number of $G$, denoted by $meg(G)$, is the minimum cardinality of such an MEG-set. This notion provides a graph theoretic model of the network monitoring problem. In this article, we compare $meg(G)$ with some other graph theoretic parameters stemming from the network monitoring problem and provide examples of graphs having prescribed values for each of these parameters. We also characterize graphs $G$ that have $V(G)$ as their minimum MEG-set, which settles an open problem due to Foucaud \textit{et al.} (CALDAM 2023), and prove that some classes of graphs fall within this characterization. We also provide a general upper bound for $meg(G)$ for sparse graphs in terms of their girth, and later refine the upper bound using the chromatic number of $G$. We examine the change in $meg(G)$ with respect to two fundamental graph operations: clique-sum and subdivisions. In both cases, we provide a lower and an upper bound of the possible amount of changes and provide (almost) tight examples.

Mots clés: Geodetic set; Monitoring edge geodetic set; k-clique sum; Subdivisions; Chromatic number; Girth

Domaines: Mathématique discrète [cs.DM]

Florent Foucaud, Pierre-Marie Marcille, Zin Mar Myint, R B Sandeep, Sagnik Sen, et al.. Bounds and extremal graphs for monitoring edge-geodetic sets in graphs. 2024. ⟨hal-04494089⟩