Partitioning a graph into a dominating set, a total dominating set, and something else

Michael A. Henning; Christian L̈owenstein; Dieter Rautenbach

doi:10.7151/dmgt.1514

Partitioning a graph into a dominating set, a total dominating set, and something else

Michael A. Henning, Christian L̈owenstein, Dieter Rautenbach

Mathematics and Applied Mathematics

Ilmenau University of Technology

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

12 Citations (Scopus)

Abstract

A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.

Original language	English
Pages (from-to)	563-574
Number of pages	12
Journal	Discussiones Mathematicae - Graph Theory
Volume	30
Issue number	4
DOIs	https://doi.org/10.7151/dmgt.1514
Publication status	Published - 2010

Keywords

Domatic number
Domination
Petersen graph
Total domination
Vertex partition

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.7151/dmgt.1514

Cite this

@article{f905359a43bc4f11a876d43bc09f221b,

title = "Partitioning a graph into a dominating set, a total dominating set, and something else",

abstract = "A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.",

keywords = "Domatic number, Domination, Petersen graph, Total domination, Vertex partition",

author = "Henning, {Michael A.} and Christian {\"L}owenstein and Dieter Rautenbach",

year = "2010",

doi = "10.7151/dmgt.1514",

language = "English",

volume = "30",

pages = "563--574",

journal = "Discussiones Mathematicae - Graph Theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

number = "4",

}

TY - JOUR

T1 - Partitioning a graph into a dominating set, a total dominating set, and something else

AU - Henning, Michael A.

AU - L̈owenstein, Christian

AU - Rautenbach, Dieter

PY - 2010

Y1 - 2010

N2 - A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.

AB - A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.

KW - Domatic number

KW - Domination

KW - Petersen graph

KW - Total domination

KW - Vertex partition

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

U2 - 10.7151/dmgt.1514

DO - 10.7151/dmgt.1514

M3 - Article

AN - SCOPUS:78649917587

SN - 1234-3099

VL - 30

SP - 563

EP - 574

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

IS - 4

ER -

Partitioning a graph into a dominating set, a total dominating set, and something else

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this