Bounds and extremal graphs for monitoring edge-geodetic sets in graphs
<|reference_start|>Bounds and extremal graphs for monitoring edge-geodetic sets in graphs: 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.<|reference_end|>
@article{foucaud2024bounds,
    title={Bounds and extremal graphs for monitoring edge-geodetic sets in graphs},
    author={Florent Foucaud, Pierre-Marie Marcille, Zin Mar Myint, R.B. Sandeep,
  Sagnik Sen, S. Taruni},
    journal={arXiv preprint arXiv:2403.09122},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.09122},
    primaryClass={cs.DM math.CO}
}