Wyszukiwarka
Abstrakt
Imagine that we are given a set D of officials and a set W of civils. For each civil x ∈ W, there must be an official v ∈ D that can serve x, and whenever any such v is serving x, there must also be another civil w ∈ W that observes v, that is, w may act as a kind of witness, to avoid any abuse from v. What is the minimum number of officials to guarantee such a service, assuming a given social network? In this paper, we introduce the concept of certified domination that models the aforementioned problem. Specifically, a dominating set D of a graph G = (VG, EG) is said to be certified if every vertex in D has either zero or at least two neighbours in VG \ D. The cardinality of a minimum certified dominating set in G is called the certified domination number of G. Herein, we present the exact values of the certified domination number for some classes of graphs as well as provide some upper bounds on this parameter for arbitrary graphs. We then characterise a wide class of graphs with equal domination and certified domination numbers and characterise graphs with large values of certified domination numbers. Next, we examine the effects on the certified domination number when the graph is modified by deleting/adding an edge or a vertex. We also provide Nordhaus–Gaddum type inequalities for the certified domination number.
Cytowania
-
8
CrossRef
-
0
Web of Science
-
1 1
Scopus
Autorzy (5)
-
Jerzy Topp
-
Radosław Ziemann
-
Paweł Żyliński
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
AKCE International Journal of Graphs and Combinatorics
nr 17,
strony 86 - 97,
ISSN: 0972-8600 - Język:
- angielski
- Rok wydania:
- 2020
- Opis bibliograficzny:
- Dettlaff M., Lemańska M., Topp J., Ziemann R., Żyliński P.: Certified domination// AKCE International Journal of Graphs and Combinatorics -Vol. 17,iss. 1 (2020), s.86-97
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.akcej.2018.09.004
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 153 razy
Publikacje, które mogą cię zainteresować
Graphs with equal domination and certified domination numbers
- M. Dettlaff,
- M. Lemańska,
- J. Topp
- + 3 autorów