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

Abstract

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)$.

15 pages