Equality in a Linear Vizing-Like Relation that Relates the Size and Total Domination Number of a Graph

Michael A. Henning, Ernst J. Joubert

Published 2011-08-30Version 1

Let $G$ be a graph each component of which has order at least 3, and let $G$ have order $n$, size $m$, total domination number $\gamma_t$ and maximum degree $\Delta(G)$. Let $\Delta = 3$ if $\Delta(G) = 2$ and $\Delta = \Delta (G)$ if $\Delta(G) \ge 3$. It is known [J. Graph Theory 49 (2005), 285--290; J. Graph Theory 54 (2007), 350--353] that $m \le \Delta (n- \gamma_t)$. In this paper we characterize the extremal graphs $G$ satisfying $m = \Delta (n- \gamma_t)$.