✦ LIBER ✦

The k-tuple domination number revisited

✍ Scribed by Vadim Zverovich

Publisher: Elsevier Science
Year: 2008
Tongue: English
Weight: 183 KB
Volume: 21
Category: Article
ISSN: 0893-9659
DOI: 10.1016/j.aml.2007.10.016

No coin nor oath required. For personal study only.

✦ Synopsis

The following fundamental result for the domination number γ (G) of a graph G was proved by Alon and Spencer, Arnautov, Lovász and Payan:

where n is the order and δ is the minimum degree of vertices of G. A similar upper bound for the double domination number was found by Harant and Henning [J. Harant, M.A. Henning, On double domination in graphs, Discuss. Math. Graph Theory 25 (2005) 29-34], and for the triple domination number by Rautenbach and Volkmann [D. Rautenbach, L. Volkmann, New bounds on the k-domination number and the k-tuple domination number, Appl. Math. Lett. 20 (2007) 98-102], who also posed the interesting conjecture on the k-tuple domination number: for any graph G with δ ≥ k -1,

where

/n is the m-degree of G. This conjecture, if true, would generalize all the mentioned upper bounds and improve an upper bound proved in [A. Gagarin, V. Zverovich, A generalised upper bound for the k-tuple domination number, Discrete Math. (2007), in press (

📜 SIMILAR VOLUMES

k-tuple domination in graphs

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

The difference between the domination nu

The difference between the domination number and the minus domination number of a cubic graph

✍ Xiaofan Yang; Qibin Hou; Xiangsheng Huang; Hengnong Xuan 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 325 KB

The closed neighborhood of a vertex subset S of a graph G = (V,E), denoted as N[Sj, is defined ss the union of S and the set of all the vertices adjacent to some vertex of S. A dominating set of a graph G = (V, E) is defined as a set S of vertices such that N[q = V. The domination number of a graph

An upper bound for the k-domination numb

An upper bound for the k-domination number of a graph

✍ E. J. Cockayne; B. Gamble; B. Shepherd 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB 👁 2 views

The kdomination number of a graph G, y k ( G ) , is the least cardinality of a set U of verticies such that any other vertex is adjacent to at least k vertices of U. We prove that if each vertex has degree at least k. then YAG) 5 kp/(k + 1).

The connected hub number and the connect

The connected hub number and the connected domination number

✍ Peter Johnson; Peter Slater; Matt Walsh 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 189 KB

The e-mail gossip number and the connect

The e-mail gossip number and the connected domination number

✍ F. Harary; B. Raghavachari 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 184 KB

## Our object is to introduce eg(G), the e-mail gossip number of a connected graph G, and derive a simple equation expressing this new invariant in terms of the known [1] connected domination number cd(G). As a corollary we see that determining each of these numbers is NP-hard. In general we follo

Upper bounds on the paired-domination nu

Upper bounds on the paired-domination number

✍ Xue-gang Chen; Wai Chee Shiu; Wai Hong Chan 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 199 KB

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The minimum cardinality of a paired-dominating set of G is the paireddomination number of G, denoted by γ pr (G). In this w