Bounds on the bondage number of a graph (Q1322182): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Domination alteration sets in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The discipline number of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The bondage number of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4014294 / rank | |||
Normal rank |
Latest revision as of 15:31, 22 May 2024
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