A note on Nordhaus-Gaddum inequalities for domination

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

18 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)83-85
Journal / PublicationDiscrete Applied Mathematics
Volume136
Issue number1
Publication statusPublished - 30 Jan 2004

Abstract

For a graph G of order n, let γ(G), γ2(G) and γt(G) be the domination, double domination and total domination numbers of G, respectively. The minimum degree of the vertices of G is denoted by δ(G) and the maximum degree by Δ(G). In this note we prove a conjecture due to Harary and Haynes saying that if a graph G has γ(G),γ(Ḡ) ≥ 4, then γ2(G) + γ 2(Ḡ) ≤ n - Δ(G) + δ(G) - 1 ≤ n - 1 and γt(G) + γt(Ḡ) ≤ n - Δ(G) + δ(G) - 1 ≤ n - 1, where Ḡ is the complement of G. © 2003 Elsevier B.V. All rights reserved.

Research Area(s)

  • Domination, Double domination, Total domination

Citation Format(s)

A note on Nordhaus-Gaddum inequalities for domination. / Erfang, Shan; Chuangyin, Dang; Liying, Kang.
In: Discrete Applied Mathematics, Vol. 136, No. 1, 30.01.2004, p. 83-85.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review