✦ LIBER ✦

Bounds on the bondage number of a graph

✍ Scribed by Bert L. Hartnell; Douglas F. Rall

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 317 KB
Volume: 128
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)90111-2

No coin nor oath required. For personal study only.

✦ Synopsis

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 bondage number is greater than its maximum degree plus one, thus showing a previously conjectured upper bound to be incorrect.

📜 SIMILAR VOLUMES

On the bondage number of a graph

✍ Yue-Li Wang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 162 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 makes the domination number of G increase. There are several papers discussed the upper bound of b(G). In this paper, we shall give an improved upper bound of b(G).

The bondage number of a graph

✍ John Frederick Fink; Michael S. Jacobson; Lael F. Kinch; John Roberts 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 654 KB

A counterexample to a conjecture on the

A counterexample to a conjecture on the bondage number of a graph

✍ Ulrich Teschner 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 113 KB

The bondage number h(G) of a nonempty graph G was first introduced by Fink, Jacobson, Kinch and Roberts in [3]. They generalized a former approach to domination-critical graphs, In their publication they conjectured that b(G)<d(G)+ 1 for any nonempty graph G.

Lower bounds on the number of triangles

Lower bounds on the number of triangles in a graph

✍ David C. Fisher 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB 👁 1 views

Bounds for the covering number of a grap

Bounds for the covering number of a graph

✍ H.L. Abbott; A.C. Liu 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 333 KB

New bounds on the edge number of a k-map

New bounds on the edge number of a k-map graph

✍ Zhi-Zhong Chen 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 310 KB 👁 1 views

## Abstract It is known that for every integer __k__ ≥ 4, each __k__‐map graph with __n__ vertices has at most __kn__ − 2__k__ edges. Previously, it was open whether this bound is tight or not. We show that this bound is tight for __k__ = 4, 5. We also show that this bound is not tight for large en