An Upper Bound for Total Domination Subdivision Numbers

Abstract

A set $S$ of vertices of a graph $G=(V,E)$ without isolated vertices is a total dominating set if every vertex of $V(G)$ is adjacent to some vertex in $S$. The total domination number ${\gamma }_t(G)$ is the minimum cardinality of a total dominating set of $G$. The total domination subdivision number $s{d}_{\gamma t}(G)$ is the minimum number of edges that must be subdivided (each edge in $G$ can be subdivided at most once) in order to increase the total domination number. In this paper, we first prove that $s{d}_{\gamma t}(G)\le n–\delta +2$ for every simple connected graph $G$ of order $n\ge 3$. We also classify all simple connected graphs $G$ with $s{d}_{\gamma t}(G)=n–\delta +2,n–\delta +1$, and $n–\delta$.