Reference request : Hoffman type bound for non-regular graph based on min and max degree

graph theoryreference-request

I'm looking for a reference for the following bound. it's relatively trivial, but I've never seen it anywhere.

Let $G$ be a graph with min degree $\delta$ and max degree at most $\Delta$. I claim that the independence number of $G$ (the largest cardinality of any set of independent vertices) satisfies
$$ \alpha(G)\leq n\left(1-\frac{\delta}{\delta+\Delta}\right) .$$

Proof Idea: I'm using Hofman's bound for non-regular graphs, based on $\lambda_\max$, the largest Laplacian eigenvalue for $G$ :
$$ \alpha(G)\leq n\left(1-\frac{\delta}{\lambda_\max}\right) .$$
see Haemers, Interlacing eigenvalues and graphs for reference. Then using Anderson, Morley, Eigenvalues of the Laplacian of a graph, for any graph $G$,
$$ \lambda_\max \leq \max_{ij \in E(G)} d_i+d_j.$$

Then let $G$ be a graph maximizing $\alpha(G)$ over all graphs with min degree $\delta$ and max degree at most $\Delta$. Assume that there exist an edge $e$ for which both end-vertices have degree strictly larger than $\delta$. Then $G'=G-e$ is still a graph with min degree $\delta$ and max degree at most $\Delta$, and as we only deleted an edge we have $\alpha(G)\leq \alpha(G')$. As $\alpha(G)$ was a maximum, then $\alpha(G)=\alpha(G')$. Therefore without loss of generality I can assume that any edge of $G$ is incident to at least one vertex of min degree. i.e.
$$ \lambda_\max \leq \max_{ij \in E(G)} d_i+d_j \leq \delta+\Delta,$$
and we get
$$ \alpha(G)\leq n\left(1-\frac{\delta}{\delta+\Delta}\right).$$

As $G$ is maximzing this value, this inequality holds for any graph with min degree $\delta$ and max degree at most $\Delta$.

Best Answer

There is a proof that does not require eigenvalues.

Let $S$ be an independent set of size $\alpha$. Then there are at least $\delta \cdot \alpha$ edges from $S$ to $V-S$. On the other hand, there are at most $\Delta \cdot (n-\alpha)$ such edges, since each vertex in $V-S$ gets at most $\Delta$ of them. Therefore $$\delta \cdot \alpha \le \Delta \cdot (n-\alpha) \implies \alpha \le n \cdot \frac{\Delta}{\delta + \Delta} = n\left(1 - \frac{\delta}{\delta+\Delta}\right).$$ For the $\delta=2$ case, this is Lemma 1 in this paper, and it can probably be found elsewhere, too.

Related Question