Geodesic
On Graphs with Disjoint Dominating and 2-Dominating Sets
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 139-146.

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

A DD2-pair of a graph G is a pair (D,D2) of disjoint sets of vertices of G such that D is a dominating set and D2 is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD2-pair, we show that every graph with minimum degree at least two has a DD2-pair. We provide a constructive characterization of trees that have a DD2-pair and show that K3,3 is the only connected graph with minimum degree at least three for which D ∪ D2 necessarily contains all vertices of the graph.
Keywords: domination, 2-domination, vertex partition 
@article{DMGT_2013_33_1_a11,
     author = {Henning, Michael A. and Rall, Douglas F.},
     title = {On {Graphs} with {Disjoint} {Dominating} and {2-Dominating} {Sets}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {139--146},
     publisher = {mathdoc},
     volume = {33},
     number = {1},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a11/}
}
TY  - JOUR
AU  - Henning, Michael A.
AU  - Rall, Douglas F.
TI  - On Graphs with Disjoint Dominating and 2-Dominating Sets
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 139
EP  - 146
VL  - 33
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a11/
LA  - en
ID  - DMGT_2013_33_1_a11
ER  - 
%0 Journal Article
%A Henning, Michael A.
%A Rall, Douglas F.
%T On Graphs with Disjoint Dominating and 2-Dominating Sets
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 139-146
%V 33
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a11/
%G en
%F DMGT_2013_33_1_a11
Henning, Michael A.; Rall, Douglas F. On Graphs with Disjoint Dominating and 2-Dominating Sets. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 139-146. http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a11/

[1] M. Dorfling, W. Goddard, M.A. Henning and C.M. Mynhardt, Construction of trees and graphs with equal domination parameters, DiscreteMath. 306 (2006) 2647-2654. doi:10.1016/j.disc.2006.04.031

[2] S.M. Hedetniemi, S.T. Hedetniemi, R.C. Laskar, L. Markus and P.J. Slater, Disjoint dominating sets in graphs, Proc. ICDM 2006, Ramanujan Mathematics Society Lecture Notes Series 7 (2008) 87-100.

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

[4] 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

[5] M.A. Henning, C. Löwenstein and D. Rautenbach, An independent dominating set in the complement of a minimum dominating set of a tree, Appl. Math. Lett. 23 (2010) 79-81. doi:10.1016/j.aml.2009.08.008

[6] M.A. Henning, C. Löwenstein and D. Rautenbach, Partitioning a graph into a dominating set, a total dominating set, and something else, Discuss. Math. Graph Theory 30 (2010) 563-574. doi:10.7151/dmgt.1514

[7] M.A. Henning and J. Southey, A note on graphs with disjoint dominating and total dominating sets, Ars Combin. 89 (2008) 159-162.

[8] M.A. Henning and J. Southey, A characterization of graphs with disjoint dominating and total dominating sets, Quaest. Math. 32 (2009) 119-129.

[9] O. Ore, Theory of Graphs: Amer. Math. Soc. Colloq. Publ., 38 (Amer. Math. Soc., Providence, RI, 1962).

[10] J. Southey and M.A. Henning, Dominating and total dominating partitions in cubic graphs, Central European J. Math. 9(3) (2011) 699-708. doi:10.7151/s11533-011-0014-2

[11] J. Southey and M.A. Henning, A characterization of graphs with disjoint dominating and paired-dominating sets, J. Comb. Optim. 22 (2011) 217-234. doi:10.1007/s10878-009-9274-1

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