On Graphs with Disjoint Dominating and 2-Dominating Sets

Michael A. Henning; Douglas F. Rall

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 1, page 139-146
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Michael A. Henning, and Douglas F. Rall. "On Graphs with Disjoint Dominating and 2-Dominating Sets." Discussiones Mathematicae Graph Theory 33.1 (2013): 139-146. <http://eudml.org/doc/268032>.

@article{MichaelA2013,
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.},
author = {Michael A. Henning, Douglas F. Rall},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination; 2-domination; vertex partition},
language = {eng},
number = {1},
pages = {139-146},
title = {On Graphs with Disjoint Dominating and 2-Dominating Sets},
url = {http://eudml.org/doc/268032},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Michael A. Henning
AU - Douglas F. Rall
TI - On Graphs with Disjoint Dominating and 2-Dominating Sets
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 1
SP - 139
EP - 146
AB - 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.
LA - eng
KW - domination; 2-domination; vertex partition
UR - http://eudml.org/doc/268032
ER -

References

top
  1. [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[Crossref] Zbl1104.05053
  2. [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. Zbl1171.05038
  3. [3] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  4. [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[WoS][Crossref] Zbl1189.05130
  5. [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[Crossref][WoS] Zbl1214.05106
  6. [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[Crossref] Zbl1217.05179
  7. [7] M.A. Henning and J. Southey, A note on graphs with disjoint dominating and total dominating sets, Ars Combin. 89 (2008) 159-162. Zbl1224.05370
  8. [8] M.A. Henning and J. Southey, A characterization of graphs with disjoint dominating and total dominating sets, Quaest. Math. 32 (2009) 119-129.[WoS][Crossref] Zbl1168.05348
  9. [9] O. Ore, Theory of Graphs: Amer. Math. Soc. Colloq. Publ., 38 (Amer. Math. Soc., Providence, RI, 1962). 
  10. [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[Crossref] Zbl1233.05151
  11. [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[Crossref][WoS] Zbl1232.05172
  12. [12] B. Zelinka, Total domatic number and degrees of vertices of a graph, Math. Slovaca 39 (1989) 7-11. Zbl0688.05066

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.