Vertices in all minimum paired-dominating sets of block graphs

Lei Chen; Changhong Lu; Zhenbing Zeng

doi:10.1007/s10878-011-9375-5

Vertices in all minimum paired-dominating sets of block graphs

Lei Chen
, Changhong Lu^*
, Zhenbing Zeng

^*Corresponding author for this work

School of Mathematical Sciences

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

3 Scopus citations

Abstract

Let G = (V ,E) be a simple graph without isolated vertices. A set S ⊄ V is a paired-dominating set if every vertex in V -S has at least one neighbor in S and the subgraph induced by S contains a perfect matching. In this paper, we present a lineartime algorithm to determine whether a given vertex in a block graph is contained in all its minimum paired-dominating sets.

Original language	English
Pages (from-to)	176-191
Number of pages	16
Journal	Journal of Combinatorial Optimization
Volume	24
Issue number	3
DOIs	https://doi.org/10.1007/s10878-011-9375-5
State	Published - Oct 2012

Keywords

Algorithm
Block graph
Domination
Paired-domination
Tree 1 I

Access to Document

10.1007/s10878-011-9375-5

Cite this

@article{0c58833c246345599e110a4852e12b8c,

title = "Vertices in all minimum paired-dominating sets of block graphs",

abstract = "Let G = (V ,E) be a simple graph without isolated vertices. A set S ⊄ V is a paired-dominating set if every vertex in V -S has at least one neighbor in S and the subgraph induced by S contains a perfect matching. In this paper, we present a lineartime algorithm to determine whether a given vertex in a block graph is contained in all its minimum paired-dominating sets.",

keywords = "Algorithm, Block graph, Domination, Paired-domination, Tree 1 I",

author = "Lei Chen and Changhong Lu and Zhenbing Zeng",

year = "2012",

month = oct,

doi = "10.1007/s10878-011-9375-5",

language = "英语",

volume = "24",

pages = "176--191",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - Vertices in all minimum paired-dominating sets of block graphs

AU - Chen, Lei

AU - Lu, Changhong

AU - Zeng, Zhenbing

PY - 2012/10

Y1 - 2012/10

N2 - Let G = (V ,E) be a simple graph without isolated vertices. A set S ⊄ V is a paired-dominating set if every vertex in V -S has at least one neighbor in S and the subgraph induced by S contains a perfect matching. In this paper, we present a lineartime algorithm to determine whether a given vertex in a block graph is contained in all its minimum paired-dominating sets.

AB - Let G = (V ,E) be a simple graph without isolated vertices. A set S ⊄ V is a paired-dominating set if every vertex in V -S has at least one neighbor in S and the subgraph induced by S contains a perfect matching. In this paper, we present a lineartime algorithm to determine whether a given vertex in a block graph is contained in all its minimum paired-dominating sets.

KW - Algorithm

KW - Block graph

KW - Domination

KW - Paired-domination

KW - Tree 1 I

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

U2 - 10.1007/s10878-011-9375-5

DO - 10.1007/s10878-011-9375-5

M3 - 文章

AN - SCOPUS:84867096581

SN - 1382-6905

VL - 24

SP - 176

EP - 191

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 3

ER -

Vertices in all minimum paired-dominating sets of block graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this