Wyniki wyszukiwania - Biblioteka Nauki

Ten serwis zostanie wyłączony 2025-02-11.

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

1 Fundamenta Informaticae

1 2024

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Perturbation results for distance-edge-monitoring numbers

100%

Yang C. , Klasing R. , He C. , Mao Y.

tom Vol. 191, nr 2

141--163

Foucaud et al. recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. Given a graph G = (V (G), E(G)), a set M ⊆ V (G) is a distance-edge-monitoring set if for every edge e ∈ E(G), there is a vertex x ∈ M and a vertex y ∈ V (G) such that the edge e belongs to all shortest paths between x and y. The smallest size of such a set in G is denoted by dem(G). Denoted by G − e (resp. G\u) the subgraph of G obtained by removing the edge e from G (resp. a vertex u together with all its incident edges from G). In this paper, we ﬁrst show that dem(G − e) − dem(G) ≤ 2 for any graph G and edge e ∈ E(G). Moreover, the bound is sharp. Next, we construct two graphs G and H to show that dem(G)−dem(G\u) and dem(H \v)−dem(H) can be arbitrarily large, where u ∈ V (G) and v ∈ V (H). We also study the relation between dem(H) and dem(G), where H is a subgraph of 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.