An Upper Bound for Total Domination Subdivision Numbers

H. Karami1, Abdollah Khodkar2, S.M. Sheikholeslami3
1Department of Mathematics Sharif University of Technology P.O. Box 11365-9415 Tehran, I.R. Iran
2Department of Mathematics University of West Georgia Carrollton, GA 30118
3 Department of Mathematics Azarbaijan University of Tarbiat Moallem Tabriz, I.R. Iran

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 \(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 first prove that \(sd_{\gamma t}(G) \leq n – \delta + 2\) for every simple connected graph \(G\) of order \(n \geq 3\). We also classify all simple connected graphs \(G\) with \(sd_{\gamma t}(G) = n – \delta + 2, n – \delta + 1\), and \(n – \delta\).