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

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.

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.