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 the normal view instead:
scientific article; zbMATH DE number 562590
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.9188687205314636
0 references
0.9038363099098206
0 references
0.8846287727355957
0 references
