×

Minimizing \(\beta+\Delta\) and well covered graphs. (English) Zbl 1071.05054

Let \(\beta , \gamma , \Delta \) be the independence number, the domination number and the maximum degree of a vertex of a graph \(G\). Let \(n\) be the number of vertices of \(G\). The inequality \(\gamma + \Delta \geq \lceil 2 \sqrt n - 1 \rceil \) is proved and the graphs attaining this minimum are studied. Further the attention is focused onto a stronger condition \(\beta + \Delta = \lceil 2 \sqrt n - 1 \rceil \).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite