Monitoring edge-geodetic sets in graphs

DOI10.1007/978-3-031-25211-2_19arXiv2210.03774MaRDI QIDQ6132539FDOQ6132539

Authors: Florent Foucaud, Krishna R. Narayanan, Lekshmi Ramasubramony Sulochana 

Publication date: 17 August 2023

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We introduce a new graph-theoretic concept in the area of network monitoring. In this area, one wishes to monitor the vertices and/or the edges of a network (viewed as a graph) in order to detect and prevent failures. Inspired by two notions studied in the literature (edge-geodetic sets and distance-edge-monitoring sets), we define the notion of a monitoring edge-geodetic set (MEG-set for short) of a graph $G$ as an edge-geodetic set $SsubseteqV(G)$ of $G$ (that is, every edge of $G$ lies on some shortest path between two vertices of $S$) with the additional property that for every edge $e$ of $G$, there is a vertex pair $x,y$ of $S$ such that $e$ lies on emph{all} shortest paths between $x$ and $y$. The motivation is that, if some edge $e$ is removed from the network (for example if it ceases to function), the monitoring probes $x$ and $y$ will detect the failure since the distance between them will increase. We explore the notion of MEG-sets by deriving the minimum size of a MEG-set for some basic graph classes (trees, cycles, unicyclic graphs, complete graphs, grids, hypercubes,...) and we prove an upper bound using the feedback edge set of the graph.

Full work available at URL: https://arxiv.org/abs/2210.03774

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Title not available (Why is that?)
• The (weighted) metric dimension of graphs: hard and easy cases
• The geodetic number of a graph
• The complexity ecology of parameters: An illustration using bounded max leaf number
• Metric dimension parameterized by max leaf number
• Strong edge geodetic problem in networks
• Network verification via routing table queries
• Parameterized complexity of geodetic set
• Edge geodetic number of a graph

Cited In (3)

• Monitoring edge-geodetic sets: hardness and graph products
• Distance-based covering problems for graphs of given cyclomatic number
• Monitoring edge-geodetic sets in graphs: extremal graphs, bounds, complexity

This page was built for publication: Monitoring edge-geodetic sets in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6132539)