PDF
Discussiones Mathematicae Graph Theory 30(3) (2010)
377-383
DOI: https://doi.org/10.7151/dmgt.1500
TOTAL OUTER-CONNECTED DOMINATION IN TREES
Joanna Cyman
Department of Technical Physics and Applied Mathematics
Gdańsk University of Technology
Narutowicza 11/12, 80-952 Gdańsk, Poland
e-mail: joana@mif.pg.gda.pl
Abstract
Let G = (V,E) be a graph. Set D ⊆ V(G) is a total outer-connected dominating set of G if D is a total dominating set in G and G[V(G)−D] is connected. The total outer-connected domination number of G, denoted by γtc(G), is the smallest cardinality of a total outer-connected dominating set of G. We show that if T is a tree of order n, then γtc(T) ≥ ⎡[2n/3]⎤. Moreover, we constructively characterize the family of extremal trees T of order n achieving this lower bound.Keywords: total outer-connected domination number, domination number.
2010 Mathematics Subject Classification: 05C05, 05C69.
References
[1] | G. Chartrand and L. Leśniak, Graphs & Digraphs (Wadsworth and Brooks/Cole, Monterey, CA, third edition, 1996). |
[2] | E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211-219, doi: 10.1002/net.3230100304. |
[3] | G.S. Domke, J.H. Hattingh, M.A. Henning and L.R. Markus, Restrained domination in trees, Discrete Math. 211 (2000) 1-9, doi: 10.1016/S0012-365X(99)00036-9. |
[4] | J.H. Hattingh, E. Jonck, E.J. Joubert and A.R. Plummer, Total Restrained Domination in Trees, Discrete Math. 307 (2007) 1643-1650, doi: 10.1016/j.disc.2006.09.014. |
[5] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). |
[6] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). |
Received 18 March 2009
Revised 27 July 2009
Accepted 17 August 2009
Close