Restrained domination in unicyclic graphs

Johannes H. Hattingh; Ernst J. Joubert; Marc Loizeaux; Andrew R. Plummer; Lucas van der Merwe

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 1, page 71-86
  • ISSN: 2083-5892

Abstract

top
Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then , and provide a characterization of graphs achieving this bound.

How to cite

top

Johannes H. Hattingh, et al. "Restrained domination in unicyclic graphs." Discussiones Mathematicae Graph Theory 29.1 (2009): 71-86. <http://eudml.org/doc/270570>.

@article{JohannesH2009,
abstract = {Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by $γ_r(G)$, is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then $γ_r(U) ≥ ⎡n/3⎤$, and provide a characterization of graphs achieving this bound.},
author = {Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas van der Merwe},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {restrained domination; unicyclic graph},
language = {eng},
number = {1},
pages = {71-86},
title = {Restrained domination in unicyclic graphs},
url = {http://eudml.org/doc/270570},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Johannes H. Hattingh
AU - Ernst J. Joubert
AU - Marc Loizeaux
AU - Andrew R. Plummer
AU - Lucas van der Merwe
TI - Restrained domination in unicyclic graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 1
SP - 71
EP - 86
AB - Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by $γ_r(G)$, is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then $γ_r(U) ≥ ⎡n/3⎤$, and provide a characterization of graphs achieving this bound.
LA - eng
KW - restrained domination; unicyclic graph
UR - http://eudml.org/doc/270570
ER -

References

top
  1. [1] G. Chartrand and L. Lesniak, Graphs & Digraphs: Fourth Edition (Chapman & Hall, Boca Raton, FL, 2005). 
  2. [2] P. Dankelmann, D. Day, J.H. Hattingh, M.A. Henning, L.R. Markus and H.C. Swart, On equality in an upper bound for the restrained and total domination numbers of a graph, to appear in Discrete Math. Zbl1138.05049
  3. [3] P. Dankelmann, J.H. Hattingh, M.A. Henning and H.C. Swart, Trees with equal domination and restrained domination numbers, J. Global Optim. 34 (2006) 597-607, doi: 10.1007/s10898-005-8565-z. Zbl1089.05056
  4. [4] G.S. Domke, J.H. Hattingh, S.T. Hedetniemi and L.R. Markus, Restrained domination in trees, Discrete Math. 211 (2000) 1-9, doi: 10.1016/S0012-365X(99)00036-9. Zbl0947.05057
  5. [5] G.S. Domke, J.H. Hattingh, M.A. Henning and L.R. Markus, Restrained domination in graphs with minimum degree two, J. Combin. Math. Combin. Comput. 35 (2000) 239-254. Zbl0971.05087
  6. [6] G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar and L.R. Markus, Restrained domination in graphs, Discrete Math. 203 (1999) 61-69, doi: 10.1016/S0012-365X(99)00016-3. Zbl1114.05303
  7. [7] J.H. Hattingh and M.A. Henning, Restrained domination excellent trees, Ars Combin. 87 (2008) 337-351. Zbl1224.05367
  8. [8] J.H. Hattingh, E. Jonck, E. J. Joubert and A.R. Plummer, Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs, Discrete Math. 308 (2008) 1080-1087, doi: 10.1016/j.disc.2007.03.061. Zbl1134.05072
  9. [9] J.H. Hattingh and A.R. Plummer, A note on restrained domination in trees, to appear in Ars Combin. Zbl1240.05045
  10. [10] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1997). Zbl0890.05002
  11. [11] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1997). 
  12. [12] M.A. Henning, Graphs with large restrained domination number, Discrete Math. 197/198 (1999) 415-429, doi: 10.1016/S0012-365X(99)90095-X. Zbl0932.05070
  13. [13] B. Zelinka, Remarks on restrained and total restrained domination in graphs, Czechoslovak Math. J. 55 (130) (2005) 393-396, doi: 10.1007/s10587-005-0029-6. Zbl1081.05050

NotesEmbed ?

top

You must be logged in to post comments.