Total domination in inflated graphs

Michael A. Henning, Adel P. Kazemi

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


The inflation GI of a graph G is obtained from G by replacing every vertex x of degree d(x) by a clique X=Kd(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 GI which come from the edges of G form a matching of GI. 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 γ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 γt( GI)<2n3, 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 γt(GI)<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 γt(GI)<n, with equality if and only if every minimum TDS of GI is a perfect total dominating set of GI, where a perfect total dominating set is a TDS with the property that every vertex is adjacent to precisely one vertex of the set.

Original languageEnglish
Pages (from-to)164-169
Number of pages6
JournalDiscrete Applied Mathematics
Issue number1-2
Publication statusPublished - Jan 2012


  • Bounds
  • Inflated graph
  • Total domination

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Total domination in inflated graphs'. Together they form a unique fingerprint.

Cite this