✦ LIBER ✦

On -tuple domination of random graphs

✍ Scribed by Bin Wang; Kai-Nan Xiang

Publisher: Elsevier Science
Year: 2009
Tongue: English
Weight: 390 KB
Volume: 22
Category: Article
ISSN: 0893-9659
DOI: 10.1016/j.aml.2009.02.004

No coin nor oath required. For personal study only.

✦ Synopsis

In graph G = (V , E), a vertex set D ⊆ V is called a domination set if any vertex u ∈ V \ D is connected to at least one vertex in D. Generally, for any natural number k, the k-tuple

The k-tuple domination number is the minimum size of k-tuple domination sets. It is known that the 1-tuple domination number (i.e. domination number) of classical random graphs G(n, p) with fixed p ∈ (0, 1) asymptotically almost surely (a.a.s.) has a two-point concentration [B. Wieland, A.P. Godbole, On the domination number of a random graph, Electron. J. Combin. 8 (2001) R37]. In this work, we prove that the 2-tuple domination number of G(n, p) with fixed p ∈ (0, 1) a.a.s. has a two-point concentration.

📜 SIMILAR VOLUMES

k-tuple domination in graphs

✍ Chung-Shou Liao; Gerard J. Chang 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 109 KB

Proof of a conjecture on -tuple dominati

Proof of a conjecture on -tuple domination in graphs

✍ Guangjun Xu; Liying Kang; Erfang Shan; Hong Yan 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 142 KB

Let G = (V, E) be a graph and N G [v] the closed neighborhood of a vertex v in G. For k ∈ N, the minimum cardinality of a set In this note we prove the following conjecture of Rautenbach and Volkmann [D. Rautenbach, L. Volkmann, New bounds on the k-domination number and the k-tuple domination numbe

R-domination on block graphs

✍ Gerard J Chang; George L Nemhauser 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 450 KB

On graphs with equal domination and inde

On graphs with equal domination and independent domination numbers

✍ Jerzy Topp; Lutz Volkmann 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 284 KB

Topp, J. and L. Volkmann, On graphs wi',h equal domination and independent domination number, Discrete Mathematics 96 (1991) 75-80. Allan and Laskar have shown that Kt.s-free graphs are graphs with equal domination and independent domination numbers. In this paper new classes of graphs with equal d

Note on 2-rainbow domination and Roman d

Note on 2-rainbow domination and Roman domination in graphs

✍ Yunjian Wu; Huaming Xing 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 244 KB

A Roman dominating function of a graph G is a function f : V → {0, 1, 2} such that every vertex with 0 has a neighbor with 2. The minimum of f (V (G)) = v∈V f (v) over all such functions is called the Roman domination number γ R (G). A 2-rainbow dominating function of a graph G is a function g that

On weakly connected domination in graphs

✍ Jean E. Dunbar; Jerrold W. Grossman; Johannes H. Hattingh; Stephen T. Hedetniemi 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 497 KB

A weakly connected dominating set for a connected graph is a dominating set D of vertices of the graph such that the edges not incident to any vertex in D do not separate the graph. This paper considers the weakly connected domination number, 7w, and related domination parameters. It is shown that t