- Tytuł:
- A Note on Non-Dominating Set Partitions in Graphs
- Autorzy:
-
Desormeaux, Wyatt J.
Haynes, Teresa W.
Henning, Michael A. - Powiązania:
- https://bibliotekanauki.pl/articles/31340558.pdf
- Data publikacji:
- 2016-11-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
domination
total domination
non-dominating partition
nontotal dominating partition - Opis:
- A set $S$ of vertices of a graph $G$ is a dominating set if every vertex not in $S$ is adjacent to a vertex of $S$ and is a total dominating set if every vertex of $G$ is adjacent to a vertex of $S$. The cardinality of a minimum dominating (total dominating) set of $G$ is called the domination (total domination) number. A set that does not dominate (totally dominate) $G$ is called a non-dominating (non-total dominating) set of $G$. A partition of the vertices of $G$ into non-dominating (non-total dominating) sets is a non-dominating (non-total dominating) set partition. We show that the minimum number of sets in a non-dominating set partition of a graph $G$ equals the total domination number of its complement $ \overline{G} $ and the minimum number of sets in a non-total dominating set partition of $G$ equals the domination number of $ \overline{G} $. This perspective yields new upper bounds on the domination and total domination numbers. We motivate the study of these concepts with a social network application.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 1043-1050
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł