Total domination in inflated graphs

The inflation GIGI of a graph GG is obtained from GG by replacing every vertex xx of degree d(x)d(x) by a clique X=Kd(x)X=Kd(x) and each edge xyxy by an edge between two vertices of the corresponding cliques XX and YY of GIGI in such a way that the edges of GIGI which come from the edges of GG form a matching of GIGI. A set SS of vertices in a graph GG is a total dominating set, abbreviated TDS, of GG if every vertex of GG is adjacent to a vertex in SS. The minimum cardinality of a TDS of GG is the total domination number γt(G)γt(G) of GG. 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 GG is a connected graph of order n≥2n≥2, then γt(GI)≥2n/3γt(GI)≥2n/3, and we characterize the graphs achieving equality in this bound. Further, if we restrict the minimum degree of GG to be at least 22, then we show that γt(GI)≥nγt(GI)≥n, with equality if and only if GG has a perfect matching. If we increase the minimum degree requirement of GG to be at least 33, then we show γt(GI)≥nγt(GI)≥n, with equality if and only if every minimum TDS of GIGI is a perfect total dominating set of GIGI, where a perfect total dominating set is a TDS with the property that every vertex is adjacent to precisely one vertex of the set.

► Total domination in the inflation GIGI of a graph GG is studied.
► If GG is connected of order n≥2n≥2, then γt(GI)≥2n/3γt(GI)≥2n/3, and the extremal graphs are characterized.
► Restriction of the minimum degree to at least 22, yields γt(GI)≥nγt(GI)≥n, with equality if and only if GG has a perfect matching.