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/

[1] B. Bollobás and E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory 3 (1979) 241-249. doi: 10.1002/jgt.3190030306

[2] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc. New York, 1998).

[3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, Inc. New York, 1998).

[4] P. Heggernes and J.A. Telle, Partitioning graphs into generalized dominating sets, Nordic J. Comput. 5 (1998) 128-142.

[5] M.A. Henning, Trees with large total domination number, Util. Math. 60 (2001) 99-106.

[6] M.A. Henning, C. Löwenstein and D. Rautenbach, Remarks about disjoint dominating sets, Discrete Math. 309 (2009) 6451-6458. doi: 10.1016/j.disc.2009.06.017

[7] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics) (Springer-Verlag, New York, 2013).

[8] C. Löwenstein and D. Rautenbach, Pairs of disjoint dominating sets in connected cubic graphs, Graphs Combin. 28 (2012) 407-421. doi: 10.1007/s00373-011-1050-1

[9] F. Uriel, M.M. Halldórsson, G. Kortsarz and A. Srinivasan, Approximating the domatic number, SIAM J. Comput. 32 (2002) 172-195. doi: 10.1137/S0097539700380754

[10] B. Zelinka, Total domatic number and degrees of vertices of a graph, Math. Slovaca 39 (1989) 7-11.

[11] B. Zelinka, Domatic numbers of graphs and their variants: A survey, in: Domination in Graphs: Advanced Topics, T.W. Haynes et al. (Ed(s)), (Marcel Dekker, New York, 1989) 351-377.