PDF

Discussiones Mathematicae Graph Theory 29(1) (2009) 71-86
DOI: https://doi.org/10.7151/dmgt.1433

RESTRAINED DOMINATION IN UNICYCLIC GRAPHS

Johannes H. Hattingh¹, Ernst J. Joubert², Marc Loizeaux³, Andrew R. Plummer⁴  and  Lucas van der Merwe³

¹Department of Mathematics and Statistics
Georgia State University
Atlanta, GA 30303-3083, USA

²Department of Mathematics
University of Johannesburg
P.O. Box 524, Auckland Park 2006, South Africa

³Department of Mathematics
University of Tennessee, Chattanooga
615 McCallie Avenue, Chattanooga, TN 37403, USA

⁴Department of Linguistics
The Ohio State University
222 Oxley Hall, 1712 Neil Avenue, Columbus, OH 43210, USA

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.

Keywords: restrained domination, unicyclic graph.

2000 Mathematics Subject Classification: 05C69.

References

[1]	G. Chartrand and L. Lesniak, Graphs & Digraphs: Fourth Edition (Chapman & Hall, Boca Raton, FL, 2005).
[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.
[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.
[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.
[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.
[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.
[7]	J.H. Hattingh and M.A. Henning, Restrained domination excellent trees, Ars Combin. 87 (2008) 337-351.
[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.
[9]	J.H. Hattingh and A.R. Plummer, A note on restrained domination in trees, to appear in Ars Combin.
[10]	T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1997).
[11]	T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1997).
[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.
[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.

Received 8 November 2007
Revised 6 October 2008
Accepted 6 October 2008