Improving a Nordhaus–Gaddum type bound for total domination using an algorithm involving vertex disjoint stars

Ernst J. Joubert

doi:10.1016/j.dam.2017.04.016

Improving a Nordhaus–Gaddum type bound for total domination using an algorithm involving vertex disjoint stars

Ernst J. Joubert

Mathematics and Applied Mathematics

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

2 Citations (Scopus)

Abstract

A Nordhaus–Gaddum-type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. In Henning et al. (2011) the authors (Henning et al.) show that if G₁⊕G₂=K(s,s), and neither G₁ nor G₂ has isolated vertices, then the product γ_t(G₁)γ_t(G₂) is at most max{8s,⌊(s+6)²∕4⌋}, where γ_t is the total domination number. In this paper we will use a vertex disjoint star covering technique, to significantly improve the mentioned bound. In particular, we will show that if G₁⊕G₂=K(s,s), and neither G₁ nor G₂ has isolated vertices, then γ_t(G₁)γ_t(G₂)≤max{8s,⌊(s+5)²∕4⌋}.

Original language	English
Pages (from-to)	95-102
Number of pages	8
Journal	Discrete Applied Mathematics
Volume	227
DOIs	https://doi.org/10.1016/j.dam.2017.04.016
Publication status	Published - 20 Aug 2017

Keywords

Nordhaus–Gaddum
Relative complement
Total domination

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2017.04.016

Cite this

@article{79a1d17b2cb74462ac3c8c4d1c70af28,

title = "Improving a Nordhaus–Gaddum type bound for total domination using an algorithm involving vertex disjoint stars",

abstract = "A Nordhaus–Gaddum-type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. In Henning et al. (2011) the authors (Henning et al.) show that if G1⊕G2=K(s,s), and neither G1 nor G2 has isolated vertices, then the product γt(G1)γt(G2) is at most max{8s,⌊(s+6)2∕4⌋}, where γt is the total domination number. In this paper we will use a vertex disjoint star covering technique, to significantly improve the mentioned bound. In particular, we will show that if G1⊕G2=K(s,s), and neither G1 nor G2 has isolated vertices, then γt(G1)γt(G2)≤max{8s,⌊(s+5)2∕4⌋}.",

keywords = "Nordhaus–Gaddum, Relative complement, Total domination",

author = "Joubert, {Ernst J.}",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier B.V.",

year = "2017",

month = aug,

day = "20",

doi = "10.1016/j.dam.2017.04.016",

language = "English",

volume = "227",

pages = "95--102",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Improving a Nordhaus–Gaddum type bound for total domination using an algorithm involving vertex disjoint stars

AU - Joubert, Ernst J.

PY - 2017/8/20

Y1 - 2017/8/20

N2 - A Nordhaus–Gaddum-type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. In Henning et al. (2011) the authors (Henning et al.) show that if G1⊕G2=K(s,s), and neither G1 nor G2 has isolated vertices, then the product γt(G1)γt(G2) is at most max{8s,⌊(s+6)2∕4⌋}, where γt is the total domination number. In this paper we will use a vertex disjoint star covering technique, to significantly improve the mentioned bound. In particular, we will show that if G1⊕G2=K(s,s), and neither G1 nor G2 has isolated vertices, then γt(G1)γt(G2)≤max{8s,⌊(s+5)2∕4⌋}.

AB - A Nordhaus–Gaddum-type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. In Henning et al. (2011) the authors (Henning et al.) show that if G1⊕G2=K(s,s), and neither G1 nor G2 has isolated vertices, then the product γt(G1)γt(G2) is at most max{8s,⌊(s+6)2∕4⌋}, where γt is the total domination number. In this paper we will use a vertex disjoint star covering technique, to significantly improve the mentioned bound. In particular, we will show that if G1⊕G2=K(s,s), and neither G1 nor G2 has isolated vertices, then γt(G1)γt(G2)≤max{8s,⌊(s+5)2∕4⌋}.

KW - Nordhaus–Gaddum

KW - Relative complement

KW - Total domination

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

U2 - 10.1016/j.dam.2017.04.016

DO - 10.1016/j.dam.2017.04.016

M3 - Article

AN - SCOPUS:85019568309

SN - 0166-218X

VL - 227

SP - 95

EP - 102

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Improving a Nordhaus–Gaddum type bound for total domination using an algorithm involving vertex disjoint stars

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this