✦ LIBER ✦

Nordhaus–Gaddum bounds on the -rainbow domatic number of a graph

✍ Scribed by D. Meierling; S.M. Sheikholeslami; L. Volkmann

Publisher: Elsevier Science
Year: 2011
Tongue: English
Weight: 212 KB
Volume: 24
Category: Article
ISSN: 0893-9659
DOI: 10.1016/j.aml.2011.04.046

No coin nor oath required. For personal study only.

✦ Synopsis

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 family on G is the k-rainbow domatic number of G, denoted by d rk (G). Note that d r1 (G) is the classical domatic number d(G). If G is a graph of order n and G is the complement of G, then we prove in this note for k ≥ 2 the Nordhaus-Gaddum inequality

This improves the Nordhaus-Gaddum bound given by Sheikholeslami and Volkmann recently.

📜 SIMILAR VOLUMES

On the Nordhaus-Gaddum Problem for the k

On the Nordhaus-Gaddum Problem for the k-Defective Chromatic Number of a Graph

✍ Nirmala Achuthan N. R. Achuthan; M. Simanihuruk 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 201 KB

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

The Roman domatic number of a graph

✍ S.M. Sheikholeslami; L. Volkmann 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 268 KB

A Roman dominating function on a graph G is a labeling f : V (G) -→ {0, 1, 2} such that every vertex with label 0 has a neighbor with label 2. A set { f 1 , f 2 , . . . , f d } of Roman dominating functions on G with the property that called a Roman dominating family (of functions) on G. The maximu

Extremal graphs for the list-coloring ve

Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum

✍ Simone Dantas; Sylvain Gravier; Frédéric Maffray 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 215 KB

We characterize the graphs G such that Ch(G) + Ch( G) = n + 1, where Ch(G) is the choice number (list-chromatic number) of G and n is its number of vertices.

Extremal graphs for the list-coloring ve

Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum

✍ Simone Dantas; Sylvain Gravier; Frederic Maffray; Bojan Mohar 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 267 KB

Bounds on the bondage number of a graph

✍ Bert L. Hartnell; Douglas F. Rall 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 317 KB

The bondage number b(G) of a graph G is the minimum cardinality of a set of edges of G whose removal from G results in a graph with domination number larger than that of G. Several new sharp upper bounds for b(G) are established. In addition, we present an infinite class of graphs each of whose bond