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

[BIBTex] [PDF] [PS]

RESTRAINED DOMINATION IN UNICYCLIC GRAPHS

Johannes H. Hattingh1, Ernst J. Joubert2, Marc Loizeaux3, Andrew R. Plummer4  and  Lucas van der Merwe3

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

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

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

4Department 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