Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let graph $G = (V, E)$ $\Rightarrow$ $\alpha(G) \ge \frac{{|V|}^{2}}{2 \times (|E| + |V|)}$, where $\alpha(G)$ is the vertex independence number of $G$.

Give some clue please!

Thanks anyway!

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

Since this is tagged homework, here's a sketch of a proof.

We can use the greedy algorithm to get a lower bound on $\alpha(G)$. At each step we choose the vertex of least degree, and place it in our independent set. We then delete it, along with its neighbours, and repeat until we run out of vertices. If the greedy algorithm runs for $t$ steps, then $\alpha(G) \geq t$. A rather slick proof that $t \geq |V(G)|/(\overline{d}+1)$, where $\overline{d}=\frac{2|E(G)|}{|V(G)|}$ is the average degree, was given in:

Halldorsson and Radhakrishnan, Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs (pdf), Algorithmica (1997) 18:145-163.

This inequality can be re-arranged to show \[\alpha(G) \geq t \geq \frac{|V(G)|^2}{2(|E(G)|+|V(G)|)}\] whenever $|E(G)| \geq |V(G)|-1$.

share|improve this answer
    
Ok, I will check this sketch. But Is it able (is it real..) to prove this without Approximating value..? Because at this moment for proving we don't use articles of this type. –  jofisher Oct 8 '12 at 8:27
    
I'm not sure what you mean, there's no approximations here. Although, I must admit, this answer seems quite difficult for a "homework" question -- possibly there's a more simple proof (it might be easier to spot if you list what topics you've been studying recently). –  Douglas S. Stones Oct 8 '12 at 8:45
    
I think it's too much to list in detail what we studied .. I can say just: Connectedness, independent set of bipartite graphs, matroids a little (I think this can be attributed to the greedy algorithm), the properties of the graph, the graphs of various types .. –  jofisher Oct 8 '12 at 22:30
    
Sorry, it's not ringing any bells for me. Perhaps someone else is able to offer a more efficient idea. –  Douglas S. Stones Oct 9 '12 at 1:54
    
I will try to understand your idea. –  jofisher Oct 9 '12 at 5:44
show 7 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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