Total domination in inflated graphs

The inflation G(I) of a graph G is obtained from G by replacing every vertex x of degree d(x) by a clique X = K(d(x)) and each edge xy by an edge between two vertices of the corresponding cliques X and Y of GI in such a way that the edges of G, which come from the edges of G form a matching of G(I). A set S of vertices in a graph G is a total dominating set, abbreviated TDS, of G if every vertex of G is adjacent to a vertex in S. The minimum cardinality of a TDS of G is the total domination number gamma(t) (G) of G. In this paper, we investigate total domination in inflated graphs. We provide an upper bound on the total domination number of an inflated graph in terms of its order and matching number. We show that if G is a connected graph of order n >= 2, then gamma(t) (G(I)) >= 2n/3, and we characterize the graphs achieving equality in this bound. Further, if we restrict the minimum degree of G to be at least 2, then we show that gamma(t) (G(I)) >= n, with equality if and only if G has a perfect matching. If we increase the minimum degree requirement of G to be at least 3, then we show gamma(t) (G(I)) >= n, with equality if and only if every minimum TDS of GI is a perfect total dominating set of G(I), where a perfect total dominating set is a TDS with the property that every vertex is adjacent to precisely one vertex of the set. (C) 2011 Elsevier B.V. All rights reserved.