On graphs with disjoint dominating and 2-dominating sets

Michael A. Henning; Douglas F. Rall

doi:10.7151/dmgt.1652

On graphs with disjoint dominating and 2-dominating sets

Michael A. Henning, Douglas F. Rall

Mathematics and Applied Mathematics

Furman University

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

6 Citations (Scopus)

Abstract

A DD₂-pair of a graph G is a pair (D,D₂) of disjoint sets of vertices of G such that D is a dominating set and D₂ is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD₂-pair, we show that every graph with minimum degree at least two has a DD₂-pair. We provide a constructive characterization of trees that have a DD₂-pair and show that K_3,3 is the only connected graph with minimum degree at least three for which D D ₂ necessarily contains all vertices of the graph.

Original language	English
Pages (from-to)	139-146
Number of pages	8
Journal	Discussiones Mathematicae - Graph Theory
Volume	33
Issue number	1
DOIs	https://doi.org/10.7151/dmgt.1652
Publication status	Published - 2013

Keywords

2-domination
Domination
Vertex partition

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.7151/dmgt.1652

Cite this

@article{82fbc6d240cd46efbf85aa1340d7cecc,

title = "On graphs with disjoint dominating and 2-dominating sets",

abstract = "A DD2-pair of a graph G is a pair (D,D2) of disjoint sets of vertices of G such that D is a dominating set and D2 is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD2-pair, we show that every graph with minimum degree at least two has a DD2-pair. We provide a constructive characterization of trees that have a DD2-pair and show that K3,3 is the only connected graph with minimum degree at least three for which D D 2 necessarily contains all vertices of the graph.",

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

author = "Henning, {Michael A.} and Rall, {Douglas F.}",

year = "2013",

doi = "10.7151/dmgt.1652",

language = "English",

volume = "33",

pages = "139--146",

journal = "Discussiones Mathematicae - Graph Theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

number = "1",

}

TY - JOUR

T1 - On graphs with disjoint dominating and 2-dominating sets

AU - Henning, Michael A.

AU - Rall, Douglas F.

PY - 2013

Y1 - 2013

N2 - A DD2-pair of a graph G is a pair (D,D2) of disjoint sets of vertices of G such that D is a dominating set and D2 is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD2-pair, we show that every graph with minimum degree at least two has a DD2-pair. We provide a constructive characterization of trees that have a DD2-pair and show that K3,3 is the only connected graph with minimum degree at least three for which D D 2 necessarily contains all vertices of the graph.

AB - A DD2-pair of a graph G is a pair (D,D2) of disjoint sets of vertices of G such that D is a dominating set and D2 is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD2-pair, we show that every graph with minimum degree at least two has a DD2-pair. We provide a constructive characterization of trees that have a DD2-pair and show that K3,3 is the only connected graph with minimum degree at least three for which D D 2 necessarily contains all vertices of the graph.

KW - 2-domination

KW - Domination

KW - Vertex partition

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

U2 - 10.7151/dmgt.1652

DO - 10.7151/dmgt.1652

M3 - Article

AN - SCOPUS:84876363090

SN - 1234-3099

VL - 33

SP - 139

EP - 146

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

IS - 1

ER -

On graphs with disjoint dominating and 2-dominating sets

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this