Monitoring edge-geodetic sets in graphs

DOI10.1007/978-3-031-25211-2_19MaRDI QIDQ6132539zbMATH OpenFDO

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)

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

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

S s u b s e t e q V (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.

Cites work

Cited in

(3)

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)