Matchings and total domination subdivision number in graphs with few induced 4-cycles

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V (G) is adjacent to some vertex in S. The total domination number γt(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdγ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. Favaron, Karami, Khoeilar and Sheikholeslami (Journal of Combinatorial Optimization, to appear) conjectured that: For any connected graph G of order n ≥ 3, sdγt(G) ≤ γt(G) + 1. In this paper we use matchings to prove this conjecture for graphs with at most three induced 4-cycles through each vertex. Corresponding author. Research supported by the Research Office of Azarbaijan University of Tarbiat Moallem. 612 O. Favaron, H. Karami, R. Khoeilar and ...