On two conjectures concerning total domination subdivision number in graphs

摘要

A subset S of vertices of a graph G without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination numbert(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision numbersdt(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 for any connected graph G of order n3, sdt(G)t(G)+1 and for any connected graph G of order n5, sdt(G) , answering two conjectures posed in Favaron et al. (J Comb Optim 20:76-84, 2010a).