𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Nordhaus–Gaddum bounds for total domination

✍ Scribed by Michael A. Henning; Ernst J. Joubert; Justin Southey

Book ID
104001098
Publisher
Elsevier Science
Year
2011
Tongue
English
Weight
227 KB
Volume
24
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

✦ Synopsis

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, and let δ * (G) denote the minimum degree among all vertices in G and G. For δ * (G) ≥ 1, we show that γ t (G)γ t (G) ≤ 2n, with equality if and only if G or G consists of disjoint copies of K 2 . When δ * (G) ∈ {2, 3, 4}, we improve the bounds on the sum and product of the total domination numbers of G and 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

A note on Nordhaus–Gaddum inequalities f
A note on Nordhaus–Gaddum inequalities for domination
✍ Shan Erfang; Dang Chuangyin; Kang Liying 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 160 KB

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

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