Author： Dorbec Paul Henning Michael A. McCoy John
Publisher： Taylor & Francis Ltd
ISSN： 1607-3606
Source： Quaestiones Mathematicae, Vol.30, Iss.1, 2007-03, pp. : 1-12
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
Let G be a graph with no isolated vertices. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S, while a paired-dominating set of G is a dominating set of vertices whose induced subgraph has a perfect matching. The maximum cardinality of a minimal total dominating set and a minimal paired-dominating set of G is the upper total domination number and upper paired-domination number of G, respectively, denoted by Γt(G) and Γpr(G). In this paper, we investigate the relationship between the upper total domination and upper paired-domination numbers of a graph. We show that for every graph G with no isolated vertex Γt(G) ≥ 1/2(Γpr(G) + 2), and we characterize the trees achieving this bound. For each positive integer k, we observe that there exist connected graphs G and H such that Γpr(G) - Γt(G) ≥ k and Γt(H) - Γpr(H) ≥ k.However for the family of trees Ton at least two vertices, we show that Γt(T) ≤ Γt(T).
Related content
Access to resources
Recommend
Graphs with large paired-domination number
Journal of Combinatorial Optimization, Vol. 13, Iss. 1, 2007-01 ,pp. :
Paired-Domination in Claw-Free Cubic Graphs
By Favaron Odile Henning Michael A.
Graphs and Combinatorics, Vol. 20, Iss. 4, 2004-11 ,pp. :