✦ LIBER ✦

Proof of a conjecture on -tuple domination in graphs

✍ Scribed by Guangjun Xu; Liying Kang; Erfang Shan; Hong Yan

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

No coin nor oath required. For personal study only.

✦ Synopsis

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 number, Appl. Math. Lett. 20 (2007)

📜 SIMILAR VOLUMES

On -tuple domination of random graphs

✍ Bin Wang; Kai-Nan Xiang 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 390 KB

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 dominatio

Proof of a conjecture on game domination

✍ O. Favaron; H. Karami; R. Khoeilar; S. M. Sheikholeslami; L. Volkmann 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 87 KB 👁 1 views

## Abstract The game domination number of a (simple, undirected) graph is defined by the following game. Two players, \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{A}}$\end{document} and \docume

Proof of a conjecture in domination theo

Proof of a conjecture in domination theory

✍ Igor E. Zverovich 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 76 KB

A dominating set D of a graph G is a least dominating set (I.d.s) if y((D)) < 2~((D~)) for any dominating set D1 (7 denotes domination number). The least domination number ~ ~ (G) of G is the minimum cardinality of a 1.d.s. We prove a conjecture of Sampathkumar (1990) that Vl ~< 3p/5 for any connect

Proof of a conjecture on irredundance pe

Proof of a conjecture on irredundance perfect graphs

✍ Lutz Volkmann; Vadim E. Zverovich 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 157 KB 👁 1 views

## Abstract Let __ir__(__G__) and γ(__G__) be the irredundance number and the domination number of a graph __G__, respectively. A graph __G__ is called __irredundance perfect__ if __ir__(__H__)=γ(__H__), for every induced subgraph __H__ of __G__. In this article we present a result which immediatel

Proof of a conjecture on cycles in a bip

Proof of a conjecture on cycles in a bipartite graph

✍ Wang, Hong 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 244 KB 👁 2 views

It was conjectured in [Wang, to appear in The Australasian Journal of Combinatorics] that, for each integer k ≥ 2, there exists . This conjecture is also verified for k = 2, 3 in [Wang, to appear; Wang, manuscript]. In this article, we prove this conjecture to be true if n ≥ 3k, i.e., M (k) ≤ 3k. W

Proof of Mader's conjecture on k-critica

Proof of Mader's conjecture on k-critical n-connected graphs

✍ Su Jianji 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB 👁 1 views

## Abstract Mader conjectured that every __k__‐critical __n__‐connected noncomplete graph __G__ has __2k__ + 2 pairwise disjoint fragments. The author in 9 proved that the conjecture holds if the order of __G__ is greater than (__k__ + 2)__n__. Now we settle this conjecture completely. © 2004 Wiley