## Abstract

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 language | English |
---|---|

Pages (from-to) | 164-169 |

Number of pages | 6 |

Journal | Discrete Applied Mathematics |

Volume | 160 |

Issue number | 1-2 |

DOIs | |

Publication status | Published - Jan 2012 |

## Keywords

- Bounds
- Inflated graph
- Total domination

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics