𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on Nordhaus–Gaddum inequalities for domination

✍ Scribed by Shan Erfang; Dang Chuangyin; Kang Liying

Book ID
104294177
Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
160 KB
Volume
136
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

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); ( G) ¿ 4, then

where G is the complement of G.

📜 SIMILAR VOLUMES

Nordhaus-Gaddum inequalities for dominat
Nordhaus-Gaddum inequalities for domination in graphs
✍ Frank Harary; Teresa W. Haynes 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 297 KB

A node in a graph G = (V,E) is said to dominate itself and all nodes adjacent to it. A set S C V is a dominating set for G if each node in V is dominated by some node in S and is a double dominating set for G if each node in V is dominated by at least two nodes in S. First we give a brief survey of

Nordhaus–Gaddum bounds for total dominat
Nordhaus–Gaddum bounds for total domination
✍ Michael A. Henning; Ernst J. Joubert; Justin Southey 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 227 KB

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 this paper we continue the study of Nordhaus-Gaddum bounds for the total domination number γ t . Let G be a graph on n vertices and let G denote the complement of G,

On a Nordhaus-Gaddum type problem for in
On a Nordhaus-Gaddum type problem for independent domination
✍ E.J. Cockayne; G. Fricke; C.M. Mynhardt 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 254 KB

Let i(G) (i(G), respectively) be the independent domination number (i.e. smallest cardinality of a maximal independent vertex subset) of the p-vertex graph G (the complement G of G, respectively). We prove limp~[max~ i(G)i(Cr)/p 2] = 1/16.

Nordhaus–Gaddum bounds on the -rainbow d
Nordhaus–Gaddum bounds on the -rainbow domatic number of a graph
✍ D. Meierling; S.M. Sheikholeslami; L. Volkmann 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 212 KB

For a positive integer k, a k-rainbow dominating function of a graph G is a function f from the vertex set V (G) to the set of all subsets of the set {1, 2, . . . , k} such that for any vertex rainbow dominating family (of functions) on G. The maximum number of functions in a k-rainbow dominating f

On Hadwiger's number— a problem of the N
On Hadwiger's number— a problem of the Nordhaus-Gaddum type
✍ M. Stiebitz 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 700 KB

Stiebitz, M., On Hadwiger's number-A problem of the Nordhaus-Gaddum type, Discrete Mathematics 101 (1992) 307-317. The Hadwiger number of a graph G = (V, E), denoted by q(G), is the maximum size of a complete graph to which G can be contracted. Let %((n, k):= {G 1 IV(G)1 = n and n(G) = k}. We shall