Discussiones Mathematicae Graph Theory 33(2) (2013) 457-459
doi: 10.7151/dmgt.1655

[BIBTex] [PDF] [PS]

Two Short Proofs on Total Domination

Allan Bickle

Department of Mathematics
Western Michigan University
1903 W. Michigan
Kalamazoo, MI 49008


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.


[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