Minimizing \(\beta + \Delta\) and Well Covered Graphs

Abstract

Let \(G\) be a graph. Let \(\gamma\) denote the minimum cardinality of a dominating set in \(G\). Let \(\beta\), respectively \(i\), denote the maximum, respectively minimum, cardinality of a maximal independent set in \(G\). We show \(\gamma + \Delta \geq \left\lceil {2\sqrt{n}-1} \right\rceil\), where \(n\) is the number of vertices of \(G\). A straightforward construction shows that given any \(G’\) there exists a graph \(G\) such that \(\gamma(G) + \Delta(G) = \left\lceil {2\sqrt{n}-1} \right\rceil\) and \(G’\) is an induced subgraph of \(G\), making classification of these \(\gamma+\Delta\) minimum graphs difficult.

We then focus on the subclass of these graphs with the stronger condition that \(\beta + \Delta = \left\lceil {2\sqrt{n}-1} \right\rceil\). For such graphs \(i = \beta\) and thus the graphs are well-covered. If \(G\) is a graph with \(\beta + \Delta = \left\lceil {2\sqrt{n}-1} \right\rceil\), we have \(\beta = \left\lceil \frac{\sqrt{n}}{\Delta+1} \right\rceil\). We give a catalogue of all well-covered graphs with \(\Delta \leq 3\) and \(\beta = \left\lceil \frac{\sqrt{n}}{\Delta+1} \right\rceil\). Again we establish that given any \(G’\) we can construct \(G\) such that \(G’\) is an induced subgraph of \(G\) and \(G\) satisfies \(\beta = \left\lceil \frac{\sqrt{n}}{\Delta+1} \right\rceil\). In fact, the graph \(G\) can be constructed so that \(\beta(G) + \Delta(G) = \left\lceil {2\sqrt{n}-1} \right\rceil\). We remark that \(\Delta(G)\) may be much larger than \(\Delta(G’)\).

We conclude the paper by analyzing integer solutions to \(\left\lceil \frac{n}{\Delta+1} \right\rceil + \Delta = \left\lceil {2\sqrt{n}-1} \right\rceil\). In particular, for each \(n\), the values of \(\Delta\) that satisfy the equation form an interval. When \(n\) is a perfect square, this interval contains only one value, namely \(\sqrt{n}\). For each \((n, \Delta)\) solution to the equation, there exists a graph \(G\) with \(n\) vertices, maximum degree \(\Delta\), and \(\beta = \left\lceil \frac{\sqrt{n}}{\Delta+1} \right\rceil\).