A characterization of (2 gamma, gamma(p))-trees

作者：Hou Xinmin^*

来源：Discrete Mathematics, 2008, 308(15): 3420-3426.

DOI：10.1016/j.disc.2007.06.034

• domination
• paired-domination
• tree

Let G = (V, E) be a graph. A set S subset of V is a dominating set of G if every vertex not in S is adjacent with some vertex in S. The domination number of G, denoted by gamma(G), is the minimum cardinality of a dominating set of G. A set S subset of V is a paired-dominating set of G if S dominates V and (S) contains at least one perfect matching. The paired-domination number of G, denoted by gamma(p)(G), is the minimum cardinality of a paired-dominating set of G. In this paper, we provide a constructive characterization of those trees for which the paired-domination number is twice the domination number.

• 出版日期2008-8-6