Connected Graphs with Maximum Total Domination Number

Abstract

The total domination number ${\gamma }_t(G)$ of graph $G=(V,E)$ is the cardinality of a smallest subset $S$ of $V$ such that every vertex of $V$ has a neighbor in $S$. It is known that, if $G$ is a connected graph with $n$ vertices, ${\gamma }_t(G)\le \lfloor 2n/3\rfloor$. Graphs achieving this bound are characterized.