Bounds on the bondage number of a graph (Q1322182)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bounds on the bondage number of a graph |
scientific article |
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