- Tytuł:
- Various Bounds for Liar’s Domination Number
- Autorzy:
-
Alimadadi, Abdollah
Mojdeh, Doost Ali
Rad, Nader Jafari - Powiązania:
- https://bibliotekanauki.pl/articles/31340859.pdf
- Data publikacji:
- 2016-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
liar’s domination
diameter
regular graph
Nordhaus-Gaddum - Opis:
- Let $ G = (V,E) $ be a graph. A set $ S \subseteq V $ is a dominating set if \( \bigcup_{v \in S} N[v] = V \), where $ N[v] $ is the closed neighborhood of $ v $. Let $ L \subseteq V $ be a dominating set, and let $v$ be a designated vertex in $V$ (an intruder vertex). Each vertex in $ L \cap N[v] $ can report that $v$ is the location of the intruder, but (at most) one $ x \in L \cap N[v] $ can report any $ w \in N[x] $ as the intruder location or $ x $ can indicate that there is no intruder in $ N[x] $. A dominating set $L$ is called a liar’s dominating set if every $ v \in V (G) $ can be correctly identified as an intruder location under these restrictions. The minimum cardinality of a liar’s dominating set is called the liar’s domination number, and is denoted by $ \gamma_{LR} (G) $. In this paper, we present sharp bounds for the liar’s domination number in terms of the diameter, the girth and clique covering number of a graph. We present two Nordhaus-Gaddum type relations for $ \gamma_{LR} (G) $, and study liar’s dominating set sensitivity versus edge-connectivity. We also present various bounds for the liar’s domination component number, that is, the maximum number of components over all minimum liar’s dominating sets.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2016, 36, 3; 629-641
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł