Estimations for the domination number of a graph
type: Item
instance of: scholarly article
title: Estimations for the domination number of a graph
zbMATH Open document ID: 0699.05055
DOI: 10.1016/0012-365X(90)90114-W
author: Lutz Volkmann
author: Peter Flach
published in: Discrete Mathematics
publication date: 1990-01-01T00:00:00Z
review text: The domination number \({\underline \beta}\)(G) of a graph G is the minimum size of a set of vertices such that every vertex of G is either in this set or adjacent to a vertex in this set. Let \({\underline \alpha}\)(G) be the maximum size of a set of vertices such that no two vertices in this set have a common neighbour. The following estimations of \({\underline \beta}\)(G) are obtained: \(2\beta (G)\leq n+1-\frac{\Delta (\delta - 1)}{\delta},\) \(2\beta (G)\leq n-(\delta -2){\underline \alpha}(G),\) \(2{\underline \beta}(G)\leq n+1-\delta.\) The last one was announced without proof by C. Payan in 1975.
reviewed by: Weixuan Li
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4145954
zbMATH Keywords: strongly independent sets
zbMATH Keywords: domination number
zbMATH Keywords: graph
MaRDI profile type: Publication
cites work: Q5422499
cites work: Q3291034
cites work: Q4108373
full work available at URL: 0012-365x(90)90114-w
OpenAlex ID: W2044521543
description: scientific article; zbMATH DE number 4145954