# Graphs with bounded degree and small max independent set

Graphs with degree $\Delta$ have a maximum independent set of size $\alpha \geqslant \frac{n}{\Delta}$ where $n$ is the number of vertices. But, are there graphs such that $\alpha \approx \frac{n}{\Delta}$, or even $\alpha = c \frac{n}{\Delta}$ for some constant $c \leqslant 1$?

First of all, the correct bound is $n/(\Delta + 1)$. This is tight for unions of cliques of size $\Delta+1$. If you want a connected graph, take a union of $\Delta$-cliques and connect them in a path or a cycle. This gives $n/\Delta$, so there is a small loss over the lower bound $n/(\Delta+1)$. If you want a connected regular graph, add a matching to the previous graph.
• Thanks, I know the "correct bound". I wrote it this way to emphasize the asymptotic flavor of the question. I can afford losing union of cliques and odd cycles! Okay, so my question was trivial indeed. But are there "many" such graphs? For instance, do random graphs with degree $\Delta$ satisfy $\alpha \leqslant c\frac{n}{\Delta}$ for some constant $c \leqslant 1$ depending only on the parameter of the random graph?
• Random $d$-regular graphs have independence number roughly $\frac{2\log d}{d} n$; the exact value of "$\frac{2\log d}{d}$" is given here: arxiv.org/pdf/1310.4787v1.pdf. Random graphs with average degree $d$ also have roughly the same independence number. See math.cmu.edu/~af1p/Texfiles/indgnp.pdf for the exact value of the constant in front of $n$. Jan 21, 2014 at 22:53