Paired-domination of Trees
Paired-domination of Trees
复制标题
DOI：
10.1023/a:1021338214295
复制
发表时间：
2003
影响因子：
1.8
通讯作者：
H. Qiao;L. Kang;M. Cardei;D. Du
中科院分区：
文献类型：
--
作者：
H. Qiao;L. Kang;M. Cardei;D. Du
设G=(V，E)是一个没有孤立顶点的图。一个集合⊂是一个准支配集，如果它控制V，则由S导出的子图包含一个完美匹配。将配对控制数γp(G)定义为配对控制集SinG的最小基数。本文给出了一种计算树的配对控制数的线性时间算法，并刻划了具有相等控制数和配对控制数的树。
Let G= (V, E) be a graph without isolated vertices. A setS⊂Vis apaired-dominatingset if it dominatesVand the subgraph induced by S,, contains a perfect matching. The paired-domination number γp(G) is defined to be the minimum cardinality of a paired-dominating setSinG. In this paper, we present a linear-time algorithm computing the paired-domination number for trees and characterize trees with equal domination and paired-domination numbers.