Estimations for the domination number of a graph
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.
scientific article; zbMATH DE number 4145954