Total domination in inflated graphs |
| |
Authors: | Michael A Henning Adel P Kazemi |
| |
Institution: | 1. Department of Mathematics, University of Johannesburg, Auckland Park 2006, South Africa;2. Department of Mathematics, University of Mohaghegh Ardabili, P. O. Box 5619911367, Ardabil, Iran |
| |
Abstract: | The inflation of a graph is obtained from by replacing every vertex of degree by a clique and each edge by an edge between two vertices of the corresponding cliques and of in such a way that the edges of which come from the edges of form a matching of . A set of vertices in a graph is a total dominating set, abbreviated TDS, of if every vertex of is adjacent to a vertex in . The minimum cardinality of a TDS of is the total domination number of . 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 is a connected graph of order , then , and we characterize the graphs achieving equality in this bound. Further, if we restrict the minimum degree of to be at least , then we show that , with equality if and only if has a perfect matching. If we increase the minimum degree requirement of to be at least , then we show , with equality if and only if every minimum TDS of is a perfect total dominating set of , where a perfect total dominating set is a TDS with the property that every vertex is adjacent to precisely one vertex of the set. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|