6
$\begingroup$

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!

1 Answers 1

3

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

  • 0
    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.2012-10-08
  • 0
    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).2012-10-08
  • 0
    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 ..2012-10-08
  • 0
    Sorry, it's not ringing any bells for me. Perhaps someone else is able to offer a more efficient idea.2012-10-09
  • 0
    I will try to understand your idea.2012-10-09
  • 0
    Yep. This proof is fine for me. I got it. Thank you for your time!2012-10-09
  • 0
    You have a mistake for $d$. $d = \frac{2|E(G)|}{|V(G)|}$. And please show how to solve that $a({H}_{1}) + a({H}_{2}) \ge \frac{|V(G)|^2}{2(|E(G)|+|V(G)|)}$. I can get only that $\ge \frac{|V(G)|}{2(|E(G)|+|V(G)|)}$..2012-10-11
  • 0
    Fixed the error. The second part is made easier with $|V(G)|^2=(|V(H_1)|+|V(H_2)|)^2=|V(H_1)|^2+2\ |V(H_1)|\ |V(H_2)|+|V(H_2)|^2$.2012-10-12
  • 0
    I know this course .. I.e. just add up fractions and convert? Ok, I will try again.2012-10-12
  • 0
    Hmm... I think there's something wrong with my arithmetic.2012-10-12
  • 0
    Indeed... my arithmetic was bogus, apologies for sending you on the wild goose chase. But, it looks like we don't even need the first part anyway (the greedy algorithm works fine with disconnected graphs).2012-10-12
  • 0
    Yep. I agree. Thanks :)2012-10-12