Minimal Graphs with Disjoint Dominating and Paired-Dominating Sets

Michael A. Henning; Jerzy Topp

doi:10.7151/dmgt.2328

Minimal Graphs with Disjoint Dominating and Paired-Dominating Sets

Michael A. Henning, Jerzy Topp

Mathematics and Applied Mathematics

State University of Applied Sciences

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

Abstract

A subset D ⊆ VG is a dominating set of G if every vertex in VG-D has a neighbor in D, while D is a paired-dominating set of G if D is a dominating set and the subgraph induced by D contains a perfect matching. A graph G is a DPDP-graph if it has a pair (D, P) of disjoint sets of vertices of G such that D is a dominating set and P is a paired-dominating set of G. The study of the DPDP-graphs was initiated by Southey and Henning [Cent. Eur. J. Math. 8 (2010) 459-467; J. Comb. Optim. 22 (2011) 217-234]. In this paper, we provide conditions which ensure that a graph is a DPDP-graph. In particular, we characterize the minimal DPDP-graphs.

Original language	English
Pages (from-to)	827-847
Number of pages	21
Journal	Discussiones Mathematicae - Graph Theory
Volume	41
Issue number	3
DOIs	https://doi.org/10.7151/dmgt.2328
Publication status	Published - 1 Aug 2021

Keywords

domination
paired-domination

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.7151/dmgt.2328

Cite this

@article{d8f35b262c4f4f9d9b5b6b450b3d8524,

title = "Minimal Graphs with Disjoint Dominating and Paired-Dominating Sets",

abstract = "A subset D ⊆ VG is a dominating set of G if every vertex in VG-D has a neighbor in D, while D is a paired-dominating set of G if D is a dominating set and the subgraph induced by D contains a perfect matching. A graph G is a DPDP-graph if it has a pair (D, P) of disjoint sets of vertices of G such that D is a dominating set and P is a paired-dominating set of G. The study of the DPDP-graphs was initiated by Southey and Henning [Cent. Eur. J. Math. 8 (2010) 459-467; J. Comb. Optim. 22 (2011) 217-234]. In this paper, we provide conditions which ensure that a graph is a DPDP-graph. In particular, we characterize the minimal DPDP-graphs.",

keywords = "domination, paired-domination",

author = "Henning, {Michael A.} and Jerzy Topp",

note = "Publisher Copyright: {\textcopyright} 2021 Michael A. Henning et al., published by Sciendo.",

year = "2021",

month = aug,

day = "1",

doi = "10.7151/dmgt.2328",

language = "English",

volume = "41",

pages = "827--847",

journal = "Discussiones Mathematicae - Graph Theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

number = "3",

}

TY - JOUR

T1 - Minimal Graphs with Disjoint Dominating and Paired-Dominating Sets

AU - Henning, Michael A.

AU - Topp, Jerzy

PY - 2021/8/1

Y1 - 2021/8/1

N2 - A subset D ⊆ VG is a dominating set of G if every vertex in VG-D has a neighbor in D, while D is a paired-dominating set of G if D is a dominating set and the subgraph induced by D contains a perfect matching. A graph G is a DPDP-graph if it has a pair (D, P) of disjoint sets of vertices of G such that D is a dominating set and P is a paired-dominating set of G. The study of the DPDP-graphs was initiated by Southey and Henning [Cent. Eur. J. Math. 8 (2010) 459-467; J. Comb. Optim. 22 (2011) 217-234]. In this paper, we provide conditions which ensure that a graph is a DPDP-graph. In particular, we characterize the minimal DPDP-graphs.

AB - A subset D ⊆ VG is a dominating set of G if every vertex in VG-D has a neighbor in D, while D is a paired-dominating set of G if D is a dominating set and the subgraph induced by D contains a perfect matching. A graph G is a DPDP-graph if it has a pair (D, P) of disjoint sets of vertices of G such that D is a dominating set and P is a paired-dominating set of G. The study of the DPDP-graphs was initiated by Southey and Henning [Cent. Eur. J. Math. 8 (2010) 459-467; J. Comb. Optim. 22 (2011) 217-234]. In this paper, we provide conditions which ensure that a graph is a DPDP-graph. In particular, we characterize the minimal DPDP-graphs.

KW - domination

KW - paired-domination

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

U2 - 10.7151/dmgt.2328

DO - 10.7151/dmgt.2328

M3 - Article

AN - SCOPUS:85120306716

SN - 1234-3099

VL - 41

SP - 827

EP - 847

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

IS - 3

ER -

Minimal Graphs with Disjoint Dominating and Paired-Dominating Sets

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this