Sharp bounds for the independence number

Details Sharp bounds for the independence number Sharp bounds for the independence number

2010-07-30

arxiv.org/abs/1007.5426v2

Mathematics

Combinatorics

12 pages

Scientific paper

For a graph $G$, the \emph{independence number} $\alpha(G)$ is the size of a largest independent set of $G$. The maximum degree of the vertices of $G$ is denoted by $\Delta(G)$. We show that for any $1 \leq k < n$, any connected graph $G$ on $n$ vertices with $\Delta(G) = k$ has % \[ \lceil \frac{n-1}{k} \rceil \leq \alpha(G) \leq n - \lceil \frac{n-1}{k} \rceil,\] % and that these bounds are sharp with the exception that when $k$ divides $n-1$ and $G$ is neither a complete graph nor a cycle, the sharp lower bound is $\frac{n-1}{k} + 1$. From this we immediately obtain sharp bounds for the independence number of any finite graph. Our proof provides an efficient algorithm for constructing an independent set of $G$ whose size is at least the lower bound for $\alpha(G)$.

Affiliated with

Also associated with

No associations

Rating

Sharp bounds for the independence number does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sharp bounds for the independence number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sharp bounds for the independence number will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-700627