A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Monitoring arc-geodetic sets of oriented graphs
Tekijät: Das, Tapas; Foucaud, Florent; Marcille, Clara; Pavan, P. D.; Sen, Sagnik
Kustantaja: Elsevier BV
Kustannuspaikka: AMSTERDAM
Julkaisuvuosi: 2025
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: Theoretical Computer Science
Lehden akronyymi: THEOR COMPUT SCI
Artikkelin numero: 115079
Vuosikerta: 1031
Sivujen määrä: 15
ISSN: 0304-3975
eISSN: 1879-2294
DOI: https://doi.org/10.1016/j.tcs.2025.115079
Verkko-osoite: https://doi.org/10.1016/j.tcs.2025.115079
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/485079690
Monitoring edge-geodetic sets in a graph are subsets of vertices such that every edge of the graph must lie on all the shortest paths between two vertices of the monitoring set. These objects were introduced in a work by Foucaud, Krishna and Ramasubramony Sulochana with relation to several prior notions in the area of network monitoring like distance edge-monitoring. In this work, we explore the extension of those notions unto oriented graphs, modelling oriented networks, and call these objects monitoring arc-geodetic sets. We also define the lower and upper monitoring arc-geodetic number of an undirected graph as the minimum and maximum of the monitoring arc-geodetic number of all orientations of the graph. We determine the monitoring arc-geodetic number of fundamental graph classes such as bipartite graphs, trees, cycles, etc. Then, we characterize the graphs for which every monitoring arc-geodetic set is the entire set of vertices, and also characterize the solutions for tournaments. We also cover some complexity aspects by studying two algorithmic problems. We show that the problem of determining if an undirected graph has an orientation with the minimal monitoring arc-geodetic set being the entire set of vertices, is NP-hard. We also show that the problem of finding a monitoring arc-geodetic set of size at most k is NP-complete when restricted to oriented graphs with maximum degree 4.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
Julkaisussa olevat rahoitustiedot:
This research was financed by the IFCAM project “Applications of graph homomorphisms” (MA/IFCAM/18/39) and SERB-MATRICS “Oriented chromatic and clique number of planar graphs” (MTR/2021/000858). Florent Foucaud was financed by the French government IDEX-ISITE initiative CAP 20-25 (ANR-16-IDEX-0001), the International Research Center “Innovation Transportation and Production Systems” of the I-SITE CAP 20-25, and the ANR project GRALMECO (ANR-21-CE48-0004). P.D. Pavan was financed by the Academy of Finland grant number 338797.
