Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets

Michael Dorfling; Wayne Goddard; Johannes H. Hattingh; Michael A. Henning

doi:10.1016/j.disc.2005.06.020

Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets

Michael Dorfling, Wayne Goddard, Johannes H. Hattingh, Michael A. Henning

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

12 Citations (Scopus)

Abstract

A total dominating set of a graph is a set of vertices such that every vertex is adjacent to a vertex in the set. We show that given a graph of order n with minimum degree at least 2, one can add at most (n-2n)/4+O(logn) edges such that the resulting graph has two disjoint total dominating sets, and this bound is best possible.

Original language	English
Pages (from-to)	82-90
Number of pages	9
Journal	Discrete Mathematics
Volume	300
Issue number	1-3
DOIs	https://doi.org/10.1016/j.disc.2005.06.020
Publication status	Published - 6 Sept 2005
Externally published	Yes

Keywords

Domatic number
Graph augmentation
Total domination

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2005.06.020

Cite this

@article{192c558c58f54fddadb50cab07c1014a,

title = "Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets",

abstract = "A total dominating set of a graph is a set of vertices such that every vertex is adjacent to a vertex in the set. We show that given a graph of order n with minimum degree at least 2, one can add at most (n-2n)/4+O(logn) edges such that the resulting graph has two disjoint total dominating sets, and this bound is best possible.",

keywords = "Domatic number, Graph augmentation, Total domination",

author = "Michael Dorfling and Wayne Goddard and Hattingh, {Johannes H.} and Henning, {Michael A.}",

year = "2005",

month = sep,

day = "6",

doi = "10.1016/j.disc.2005.06.020",

language = "English",

volume = "300",

pages = "82--90",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets

AU - Dorfling, Michael

AU - Goddard, Wayne

AU - Hattingh, Johannes H.

AU - Henning, Michael A.

PY - 2005/9/6

Y1 - 2005/9/6

N2 - A total dominating set of a graph is a set of vertices such that every vertex is adjacent to a vertex in the set. We show that given a graph of order n with minimum degree at least 2, one can add at most (n-2n)/4+O(logn) edges such that the resulting graph has two disjoint total dominating sets, and this bound is best possible.

AB - A total dominating set of a graph is a set of vertices such that every vertex is adjacent to a vertex in the set. We show that given a graph of order n with minimum degree at least 2, one can add at most (n-2n)/4+O(logn) edges such that the resulting graph has two disjoint total dominating sets, and this bound is best possible.

KW - Domatic number

KW - Graph augmentation

KW - Total domination

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

U2 - 10.1016/j.disc.2005.06.020

DO - 10.1016/j.disc.2005.06.020

M3 - Article

AN - SCOPUS:25444500982

SN - 0012-365X

VL - 300

SP - 82

EP - 90

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this