Paired-domination of Trees |
| |
| Authors: | Hong Qiao Liying Kang Mihaela Cardei Ding-Zhu Du |
| |
| Institution: | (1) Department of Manufacturing Engineering and Engineering Management, City University of Hong Kong, Hong Kong, China;(2) Department of Mathematics, Shanghai University, Shanghai, 200436, 3, China;(3) Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455, USA |
| |
| Abstract: | Let G= (V, E) be a graph without isolated vertices. A set S V is a paired-dominating set if it dominates V and the subgraph induced by S, S , contains a perfect matching. The paired-domination number  p(G) is defined to be the minimum cardinality of a paired-dominating set S in G. 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
