✦ LIBER ✦

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

✍ Scribed by Ulrich Teschner

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 113 KB
Volume: 122
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90317-m

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 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

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

A counterexample to a conjecture of meyn

A counterexample to a conjecture of meyniel on kernel-perfect graphs

✍ Hortensia Galeana-Sánchez 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 237 KB

A counterexample to the bold conjecture

✍ Sakuma, Tadashi 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 83 KB 👁 1 views

A pair of vertices (x, y) of a graph G is an ω-critical pair if ω(G + xy) > ω(G), where G + xy denotes the graph obtained by adding the edge xy to G and ω(H) is the clique number of H. The ω-critical pairs are never edges in G. A maximal stable set S of G is called a forced color class of G if S mee

A counterexample to a conjecture of gran

A counterexample to a conjecture of grant

✍ Mao-cheng Cai 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 74 KB

We give a counterexample to the following conjecture of Douglas D. Grant Cl]: If a positive integer t 3 2 and D is a strict digraph of order 2t such that S+(D) 3 t and S'(D)2 t, then D has an anti-directed hamiltonian cycle. Where S+(D) and 6-(D) denote the minimum indegree and outdegree, respective