Upper bounds on the paired-domination number

Xue gang Chen; Wai Chee Shiu; Wai Hong Chan

doi:10.1016/j.aml.2007.10.029

Upper bounds on the paired-domination number

Xue gang Chen^*, Wai Chee Shiu, Wai Hong Chan

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Journal article › peer-review

11 Citations (Scopus)

Abstract

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The minimum cardinality of a paired-dominating set of G is the paired-domination number of G, denoted by γ_{p r} (G). In this work, we present several upper bounds on the paired-domination number in terms of the maximum degree, minimum degree, girth and order.

Original language	English
Pages (from-to)	1194-1198
Number of pages	5
Journal	Applied Mathematics Letters
Volume	21
Issue number	11
DOIs	https://doi.org/10.1016/j.aml.2007.10.029
Publication status	Published - Nov 2008

Scopus Subject Areas

Applied Mathematics

User-Defined Keywords

Girth
Maximum degree
Minimum degree
Paired-domination number

Access to Document

10.1016/j.aml.2007.10.029

Cite this

@article{0992a264b3ae49f2acbb167204d36146,

title = "Upper bounds on the paired-domination number",

abstract = "A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The minimum cardinality of a paired-dominating set of G is the paired-domination number of G, denoted by γp r (G). In this work, we present several upper bounds on the paired-domination number in terms of the maximum degree, minimum degree, girth and order.",

keywords = "Girth, Maximum degree, Minimum degree, Paired-domination number",

author = "Chen, {Xue gang} and Shiu, {Wai Chee} and Chan, {Wai Hong}",

note = "Funding Information: This work was partially supported by the CERG Research Grant Council of Hong Kong and the Faculty Research Grant of Hong Kong Baptist University. It was supported by a Doctoral Research Grant of North China Electric Power University (200722026).",

year = "2008",

month = nov,

doi = "10.1016/j.aml.2007.10.029",

language = "English",

volume = "21",

pages = "1194--1198",

journal = "Applied Mathematics Letters",

issn = "0893-9659",

publisher = "Elsevier Ltd.",

number = "11",

}

TY - JOUR

T1 - Upper bounds on the paired-domination number

AU - Chen, Xue gang

AU - Shiu, Wai Chee

AU - Chan, Wai Hong

N1 - Funding Information: This work was partially supported by the CERG Research Grant Council of Hong Kong and the Faculty Research Grant of Hong Kong Baptist University. It was supported by a Doctoral Research Grant of North China Electric Power University (200722026).

PY - 2008/11

Y1 - 2008/11

N2 - A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The minimum cardinality of a paired-dominating set of G is the paired-domination number of G, denoted by γp r (G). In this work, we present several upper bounds on the paired-domination number in terms of the maximum degree, minimum degree, girth and order.

AB - A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The minimum cardinality of a paired-dominating set of G is the paired-domination number of G, denoted by γp r (G). In this work, we present several upper bounds on the paired-domination number in terms of the maximum degree, minimum degree, girth and order.

KW - Girth

KW - Maximum degree

KW - Minimum degree

KW - Paired-domination number

UR - http://www.scopus.com/inward/record.url?scp=51049100586&partnerID=8YFLogxK

U2 - 10.1016/j.aml.2007.10.029

DO - 10.1016/j.aml.2007.10.029

M3 - Journal article

AN - SCOPUS:51049100586

SN - 0893-9659

VL - 21

SP - 1194

EP - 1198

JO - Applied Mathematics Letters

JF - Applied Mathematics Letters

IS - 11

ER -

Upper bounds on the paired-domination number

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this