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

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

73 Citations (Scopus)

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. © 2003 Kluwer Academic Publishers.

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

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

This work was supported by the National Nature Science Foundation of China No. 10101010.

Access Output

10.1023/A:1021338214295

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{a2e62e1f82714f04bda7c1e07bc4247b,

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. {\textcopyright} 2003 Kluwer Academic Publishers.",

author = "Hong Qiao and Liying Kang and Mihaela Cardei and Ding-Zhu Du",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "2003",

month = jan,

doi = "10.1023/A:1021338214295",

language = "English",

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

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

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. © 2003 Kluwer Academic Publishers.

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. © 2003 Kluwer Academic Publishers.

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

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84867942679&origin=recordpage

U2 - 10.1023/A:1021338214295

DO - 10.1023/A:1021338214295

M3 - RGC 21 - Publication in refereed journal

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

Bibliographical note

Funding

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this