Total Domination in Graphs with Diameter 2
Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. Henning, Anders Yeo · Journal of Graph Theory · 2013
The total domination number of a graph G is the minimum cardinality of a set S of vertices, so that every vertex of G is adjacent to a vertex in S. In this article, we determine an optimal upper bound on the total domination number of a graph with diameter 2. We show that for every graph G on n vertices with diameter 2, . This bound is optimal in the sense that given any , there exist graphs G with diameter 2 of all sufficiently large even orders n such that .