An Algorithm for Monitoring Edge-geodetic Sets in Chordal Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910111568494592 |
|---|---|
| author | Marcille, Clara Oijid, Nacim |
| author_facet | Marcille, Clara Oijid, Nacim |
| contents | A monitoring edge-geodetic set (or meg-set for short) of a graph is a set of vertices $M$ such that if any edge is removed, then the distance between some two vertices of $M$ increases. This notion was introduced by Foucaud et al. in 2023 as a way to monitor networks for communication failures. As computing a minimum meg-set is hard in general, recent works aimed to find polynomial-time algorithms to compute minimum meg-sets when the input belongs to a restricted class of graphs. Most of these results are based on the property of some classes of graphs to admit a unique minimal meg-set, which is then easy to compute. In this work, we prove that chordal graphs also admit a unique minimal meg-set, answering a standing open question of Foucaud et al. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_03288 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Algorithm for Monitoring Edge-geodetic Sets in Chordal Graphs Marcille, Clara Oijid, Nacim Discrete Mathematics Computational Complexity A monitoring edge-geodetic set (or meg-set for short) of a graph is a set of vertices $M$ such that if any edge is removed, then the distance between some two vertices of $M$ increases. This notion was introduced by Foucaud et al. in 2023 as a way to monitor networks for communication failures. As computing a minimum meg-set is hard in general, recent works aimed to find polynomial-time algorithms to compute minimum meg-sets when the input belongs to a restricted class of graphs. Most of these results are based on the property of some classes of graphs to admit a unique minimal meg-set, which is then easy to compute. In this work, we prove that chordal graphs also admit a unique minimal meg-set, answering a standing open question of Foucaud et al. |
| title | An Algorithm for Monitoring Edge-geodetic Sets in Chordal Graphs |
| topic | Discrete Mathematics Computational Complexity |
| url | https://arxiv.org/abs/2602.03288 |