DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 33(1) (2013) 139-146
DOI: https://doi.org/10.7151/dmgt.1652

This paper is dedicated to Mietek Borowiecki on the occasion of his 70th
birthday. We thank him for his warmth and kindness to us, for his inspiration,
and for his dedication to graph theory.

On graphs with disjoint dominating and 2-dominating sets

Michael A. Henning

Department of Mathematics
University of Johannesburg
Auckland Park, 2006 South Africa

Douglas F. Rall

Department of Mathematics
Furman University
Greenville, SC, USA

Abstract

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

2010 Mathematics Subject Classification: 05C69.

References

[1]M. Dorfling, W. Goddard, M.A. Henning and C.M. Mynhardt, Construction of trees and graphs with equal domination parameters, Discrete Math. 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.2478/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.

Received 28 February 2012
Revised 2 October 2012
Accepted 31 October 2012

Close