Bounds on the bondage number of a graph
type: Item
instance of: scholarly article
title: Bounds on the bondage number of a graph
zbMATH Open document ID: 0796.05051
DOI: 10.1016/0012-365X(94)90111-2
author: Bert L. Hartnell
author: Douglas F. Rall
published in: Discrete Mathematics
publication date: 1994-09-15T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 562590
zbMATH Keywords: bondage number
zbMATH Keywords: domination number
zbMATH Keywords: upper bounds
zbMATH Keywords: maximum degree
MaRDI profile type: Publication
cites work: Domination alteration sets in graphs
cites work: The discipline number of a graph
cites work: The bondage number of a graph
cites work: Q4014294
description: scientific article; zbMATH DE number 562590