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$?


1 Answer 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.

  • $\begingroup$ 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? $\endgroup$
    – user
    Commented Jan 21, 2014 at 21:00
  • $\begingroup$ 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$. $\endgroup$ Commented Jan 21, 2014 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.