A characterization of graphs with disjoint dominating and paired-dominating sets

Justin Southey; Michael A. Henning

doi:10.1007/s10878-009-9274-1

A characterization of graphs with disjoint dominating and paired-dominating sets

Justin Southey, Michael A. Henning

University of KwaZulu-Natal

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

9 Citations (Scopus)

Abstract

A dominating set of a graph is a set of vertices such that every vertex not in the set is adjacent to a vertex in the set, while a paired-dominating set of a graph is a set of vertices such that every vertex is adjacent to a vertex in the set and the subgraph induced by the set contains a perfect matching. In this paper, we provide a constructive characterization of graphs whose vertex set can be partitioned into a dominating set and a paired-dominating set.

Original language	English
Pages (from-to)	217-234
Number of pages	18
Journal	Journal of Combinatorial Optimization
Volume	22
Issue number	2
DOIs	https://doi.org/10.1007/s10878-009-9274-1
Publication status	Published - Aug 2011
Externally published	Yes

Keywords

Domination
Paired-domination
Vertex partition

ASJC Scopus subject areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1007/s10878-009-9274-1

Cite this

@article{6aa0b309005f4747b76b34d4edf08e03,

title = "A characterization of graphs with disjoint dominating and paired-dominating sets",

abstract = "A dominating set of a graph is a set of vertices such that every vertex not in the set is adjacent to a vertex in the set, while a paired-dominating set of a graph is a set of vertices such that every vertex is adjacent to a vertex in the set and the subgraph induced by the set contains a perfect matching. In this paper, we provide a constructive characterization of graphs whose vertex set can be partitioned into a dominating set and a paired-dominating set.",

keywords = "Domination, Paired-domination, Vertex partition",

author = "Justin Southey and Henning, {Michael A.}",

year = "2011",

month = aug,

doi = "10.1007/s10878-009-9274-1",

language = "English",

volume = "22",

pages = "217--234",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - A characterization of graphs with disjoint dominating and paired-dominating sets

AU - Southey, Justin

AU - Henning, Michael A.

PY - 2011/8

Y1 - 2011/8

N2 - A dominating set of a graph is a set of vertices such that every vertex not in the set is adjacent to a vertex in the set, while a paired-dominating set of a graph is a set of vertices such that every vertex is adjacent to a vertex in the set and the subgraph induced by the set contains a perfect matching. In this paper, we provide a constructive characterization of graphs whose vertex set can be partitioned into a dominating set and a paired-dominating set.

AB - A dominating set of a graph is a set of vertices such that every vertex not in the set is adjacent to a vertex in the set, while a paired-dominating set of a graph is a set of vertices such that every vertex is adjacent to a vertex in the set and the subgraph induced by the set contains a perfect matching. In this paper, we provide a constructive characterization of graphs whose vertex set can be partitioned into a dominating set and a paired-dominating set.

KW - Domination

KW - Paired-domination

KW - Vertex partition

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

U2 - 10.1007/s10878-009-9274-1

DO - 10.1007/s10878-009-9274-1

M3 - Article

AN - SCOPUS:80051696785

SN - 1382-6905

VL - 22

SP - 217

EP - 234

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 2

ER -

A characterization of graphs with disjoint dominating and paired-dominating sets

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this