Nordhaus-Gaddum bounds for total domination

Michael A. Henning; Ernst J. Joubert; Justin Southey

doi:10.1016/j.aml.2011.01.011

Nordhaus-Gaddum bounds for total domination

Michael A. Henning, Ernst J. Joubert, Justin Southey

Mathematics and Applied Mathematics

University of Johannesburg

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

6 Citations (Scopus)

Abstract

A NordhausGaddum-type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. In this paper we continue the study of NordhausGaddum bounds for the total domination number γt. Let G be a graph on n vertices and let Ḡ denote the complement of G, and let δ*(G) denote the minimum degree among all vertices in G and Ḡ. For δ*(G)<1, we show that γ_t (G)γ _t (Ḡ)≤2n, with equality if and only if G or Ḡ consists of disjoint copies of K2. When δ*(G)∈2,3,4, we improve the bounds on the sum and product of the total domination numbers of G and Ḡ.

Original language	English
Pages (from-to)	987-990
Number of pages	4
Journal	Applied Mathematics Letters
Volume	24
Issue number	6
DOIs	https://doi.org/10.1016/j.aml.2011.01.011
Publication status	Published - Jun 2011

Keywords

NordhausGaddum
Total domination

ASJC Scopus subject areas

Applied Mathematics

Access to Document

10.1016/j.aml.2011.01.011

Cite this

@article{c43c3045164e43fea647a23134897ba4,

title = "Nordhaus-Gaddum bounds for total domination",

abstract = "A NordhausGaddum-type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. In this paper we continue the study of NordhausGaddum bounds for the total domination number γt. Let G be a graph on n vertices and let Ḡ denote the complement of G, and let δ*(G) denote the minimum degree among all vertices in G and Ḡ. For δ*(G)<1, we show that γt (G)γ t (Ḡ)≤2n, with equality if and only if G or Ḡ consists of disjoint copies of K2. When δ*(G)∈2,3,4, we improve the bounds on the sum and product of the total domination numbers of G and Ḡ.",

keywords = "NordhausGaddum, Total domination",

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

year = "2011",

month = jun,

doi = "10.1016/j.aml.2011.01.011",

language = "English",

volume = "24",

pages = "987--990",

journal = "Applied Mathematics Letters",

issn = "0893-9659",

publisher = "Elsevier Ltd.",

number = "6",

}

TY - JOUR

T1 - Nordhaus-Gaddum bounds for total domination

AU - Henning, Michael A.

AU - Joubert, Ernst J.

AU - Southey, Justin

PY - 2011/6

Y1 - 2011/6

N2 - A NordhausGaddum-type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. In this paper we continue the study of NordhausGaddum bounds for the total domination number γt. Let G be a graph on n vertices and let Ḡ denote the complement of G, and let δ*(G) denote the minimum degree among all vertices in G and Ḡ. For δ*(G)<1, we show that γt (G)γ t (Ḡ)≤2n, with equality if and only if G or Ḡ consists of disjoint copies of K2. When δ*(G)∈2,3,4, we improve the bounds on the sum and product of the total domination numbers of G and Ḡ.

AB - A NordhausGaddum-type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. In this paper we continue the study of NordhausGaddum bounds for the total domination number γt. Let G be a graph on n vertices and let Ḡ denote the complement of G, and let δ*(G) denote the minimum degree among all vertices in G and Ḡ. For δ*(G)<1, we show that γt (G)γ t (Ḡ)≤2n, with equality if and only if G or Ḡ consists of disjoint copies of K2. When δ*(G)∈2,3,4, we improve the bounds on the sum and product of the total domination numbers of G and Ḡ.

KW - NordhausGaddum

KW - Total domination

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

U2 - 10.1016/j.aml.2011.01.011

DO - 10.1016/j.aml.2011.01.011

M3 - Article

AN - SCOPUS:79952438491

SN - 0893-9659

VL - 24

SP - 987

EP - 990

JO - Applied Mathematics Letters

JF - Applied Mathematics Letters

IS - 6

ER -

Nordhaus-Gaddum bounds for total domination

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this