A note on Nordhaus-Gaddum inequalities for domination

Shan Erfang; Dang Chuangyin; Kang Liying

doi:10.1016/S0166-218X(03)00200-2

A note on Nordhaus-Gaddum inequalities for domination

Shan Erfang
, Dang Chuangyin
, Kang Liying

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

18 Citations (Scopus)

Abstract

For a graph G of order n, let γ(G), γ₂(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 γ₂(G) + γ ₂(Ḡ) ≤ 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.

Original language	English
Pages (from-to)	83-85
Journal	Discrete Applied Mathematics
Volume	136
Issue number	1
DOIs	https://doi.org/10.1016/S0166-218X(03)00200-2
Publication status	Published - 30 Jan 2004

Research Keywords

Domination
Double domination
Total domination

Access Output

10.1016/S0166-218X(03)00200-2Licence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{7b784e4f8dff4113a98e5321d41e7d8d,

title = "A note on Nordhaus-Gaddum inequalities for domination",

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. {\textcopyright} 2003 Elsevier B.V. All rights reserved.",

keywords = "Domination, Double domination, Total domination",

author = "Shan Erfang and Dang Chuangyin and Kang Liying",

year = "2004",

month = jan,

day = "30",

doi = "10.1016/S0166-218X(03)00200-2",

language = "English",

volume = "136",

pages = "83--85",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - A note on Nordhaus-Gaddum inequalities for domination

AU - Erfang, Shan

AU - Chuangyin, Dang

AU - Liying, Kang

PY - 2004/1/30

Y1 - 2004/1/30

N2 - 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.

AB - 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.

KW - Domination

KW - Double domination

KW - Total domination

UR - https://www.scopus.com/pages/publications/0346331133

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0346331133&origin=recordpage

U2 - 10.1016/S0166-218X(03)00200-2

DO - 10.1016/S0166-218X(03)00200-2

M3 - RGC 21 - Publication in refereed journal

SN - 0166-218X

VL - 136

SP - 83

EP - 85

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1

ER -

A note on Nordhaus-Gaddum inequalities for domination

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this