A note on Nordhaus-Gaddum inequalities for domination
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 83-85 |
Journal / Publication | Discrete Applied Mathematics |
Volume | 136 |
Issue number | 1 |
Publication status | Published - 30 Jan 2004 |
Link(s)
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.
In: Discrete Applied Mathematics, Vol. 136, No. 1, 30.01.2004, p. 83-85.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review