Geodesic
A Note on Non-Dominating Set Partitions in Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 1043-1050

Voir la notice de l'article provenant de la source Library of Science

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 G and the minimum number of sets in a non-total dominating set partition of G equals the domination number of 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.
Keywords: domination, total domination, non-dominating partition, nontotal dominating partition 
@article{DMGT_2016_36_4_a19,
     author = {Desormeaux, Wyatt J. and Haynes, Teresa W. and Henning, Michael A.},
     title = {A {Note} on {Non-Dominating} {Set} {Partitions} in {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1043--1050},
     publisher = {mathdoc},
     volume = {36},
     number = {4},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a19/}
}
TY  - JOUR
AU  - Desormeaux, Wyatt J.
AU  - Haynes, Teresa W.
AU  - Henning, Michael A.
TI  - A Note on Non-Dominating Set Partitions in Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 1043
EP  - 1050
VL  - 36
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a19/
LA  - en
ID  - DMGT_2016_36_4_a19
ER  - 
%0 Journal Article
%A Desormeaux, Wyatt J.
%A Haynes, Teresa W.
%A Henning, Michael A.
%T A Note on Non-Dominating Set Partitions in Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 1043-1050
%V 36
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a19/
%G en
%F DMGT_2016_36_4_a19
Desormeaux, Wyatt J.; Haynes, Teresa W.; Henning, Michael A. A Note on Non-Dominating Set Partitions in Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 1043-1050. http://geodesic.mathdoc.fr/item/DMGT_2016_36_4_a19/