Minimizing $\beta +\mathrm{\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 +\mathrm{\Delta }\ge \lceil 2\sqrt{n}-1\rceil$, where $n$ is the number of vertices of $G$. A straightforward construction shows that given any $G^{\prime }$ there exists a graph $G$ such that $\gamma (G)+\mathrm{\Delta }(G)=\lceil 2\sqrt{n}-1\rceil$ and $G^{\prime }$ is an induced subgraph of $G$, making classification of these $\gamma +\mathrm{\Delta }$ minimum graphs difficult.

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

We conclude the paper by analyzing integer solutions to $\lceil \frac{n}{\mathrm{\Delta }+1}\rceil +\mathrm{\Delta }=\lceil 2\sqrt{n}-1\rceil$. In particular, for each $n$, the values of $\mathrm{\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,\mathrm{\Delta })$ solution to the equation, there exists a graph $G$ with $n$ vertices, maximum degree $\mathrm{\Delta }$, and $\beta =\lceil \frac{\sqrt{n}}{\mathrm{\Delta }+1}\rceil$.