PDF
Discussiones Mathematicae Graph Theory 33(2) (2013)
457-459
DOI: https://doi.org/10.7151/dmgt.1655
Two Short Proofs on Total Domination
| Allan Bickle
Department of Mathematics |
Abstract
A set of vertices of a graph G is a total dominating set if each vertex of G is adjacent to a vertex in the set. The total domination number of a graph γt(G) is the minimum size of a total dominating set. We provide a short proof of the result that γt(G) ≤ 2n/3 for connected graphs with n ≥ 3 and a short characterization of the extremal graphs.
Keywords: total domination
2010 Mathematics Subject Classification: 05C69.
References
| [1] | R.C. Brigham, J.R. Carrington and R.P. Vitray, Connected graphs with maximum total domination number, J. Combin. Comput. Combin. Math. 34 (2000) 81--96. |
| [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] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc, 1998). |
Received 1 July 2011
Revised 22 December 2011
Accepted 13 March 2012
Close