Bounds on the bondage number of a graph (Q1322182)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Bounds on the bondage number of a graph |
scientific article; zbMATH DE number 562590
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Bounds on the bondage number of a graph |
scientific article; zbMATH DE number 562590 |
Statements
Bounds on the bondage number of a graph (English)
0 references
15 September 1994
0 references
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\). In this paper several new sharp upper bounds for \(b(G)\) are established and an infinite class of graphs each of whose bondage number is greater than its maximum degree plus one is presented. This shows that Fink's conjecture is incorrect.
0 references
bondage number
0 references
domination number
0 references
upper bounds
0 references
maximum degree
0 references
