Volume 37 • Number 1 • 2014   • On the Total Domination Subdivision Number in Graphs O. Favaron, H. Karami, R. Khoeilar and S. M. Sheikholeslami Abstract. A set $S\subseteq V$ of vertices in a graph $G=(V,E)$ without isolated vertices is a {\em total dominating set} if every vertex of $V$ is adjacent to some vertex in $S$. The {\em total domination number} $\gamma_t(G)$ is the minimum cardinality of a total dominating set of $G$. The {\em total domination subdivision number} ${\rm sd}_{\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 prove that ${\rm sd}_{\gamma_t}(G)\le \alpha'(G)+1$ for some classes of graphs where $\alpha '(G)$ is the maximum cardinality of a matching of $G$. 2010 Mathematics Subject Classification: 05C69 Full text: PDF