Paired-domination of trees

Hong Qiao; Liying Kang; Mihaela Cardei; Ding Zhu Du

doi:10.1023/A:1021338214295

Paired-domination of trees

Hong Qiao
, Liying Kang
, Mihaela Cardei
, Ding Zhu Du

City University of Hong Kong
Shanghai University
University of Minnesota Twin Cities

Research output: Contribution to journal › Article › peer-review

73 Scopus citations

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.

Original language	English
Pages (from-to)	43-54
Number of pages	12
Journal	Journal of Global Optimization
Volume	25
Issue number	1
DOIs	https://doi.org/10.1023/A:1021338214295
State	Published - Jan 2003
Externally published	Yes

Access to Document

10.1023/A:1021338214295

Cite this

@article{9e7de04168f04e5581dbf7a886eb2cc2,

title = "Paired-domination of trees",

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.",

author = "Hong Qiao and Liying Kang and Mihaela Cardei and Du, \{Ding Zhu\}",

year = "2003",

month = jan,

doi = "10.1023/A:1021338214295",

language = "英语",

volume = "25",

pages = "43--54",

journal = "Journal of Global Optimization",

issn = "0925-5001",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

T1 - Paired-domination of trees

AU - Qiao, Hong

AU - Kang, Liying

AU - Cardei, Mihaela

AU - Du, Ding Zhu

PY - 2003/1

Y1 - 2003/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84867942679

U2 - 10.1023/A:1021338214295

DO - 10.1023/A:1021338214295

M3 - 文章

AN - SCOPUS:84867942679

SN - 0925-5001

VL - 25

SP - 43

EP - 54

JO - Journal of Global Optimization

JF - Journal of Global Optimization

IS - 1

ER -

Paired-domination of trees

Abstract

Access to Document

Other files and links

Cite this