Perturbation results for distance-edge-monitoring numbers

Abstract: Foucaud et al. recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. Let

G = (V, E)

be a graph. A set of vertices

M s u b s e t e q V (G)

is a distance-edge-monitoring set of

G

if any edges in

G

can be monitored by a vertex in

M

. The distance-edge-monitoring number

o p e r a t o r n a m e d e m (G)

is the minimum cardinality of a distance-edge-monitoring set of

G

. In this paper, we first show that

o p e r a t o r n a m e d e m (G s e t m i n u s e) - o p e r a t o r n a m e d e m (G) l e q 2

for any graph

G

and edge

e i n E (G)

. Moreover, the bound is sharp. Next, we construct two graphs

G

and

H

to show that

o p e r a t o r n a m e d e m (G) - o p e r a t o r n a m e d e m (G - u)

and

o p e r a t o r n a m e d e m (H - v) - o p e r a t o r n a m e d e m (H)

can be arbitrarily large, where

u i n V (G)

and

v i n V (H)

. We also study the relationship between

o p e r a t o r n a m e d e m (H)

and

o p e r a t o r n a m e d e m (G)

for

H s u b s e t G

. In the end, we give an algorithm to judge whether the distance-edge-monitoring set still remain in the resulting graph when any edge of a graph

G

is deleted.

This page was built for publication: Perturbation results for distance-edge-monitoring numbers