Welcome to MathOverflow

Question

1

If $G$ is a graph with $n$ vertices and $\frac{nk}{2}$ edges, $k\ge -1,$ then $a(G)\ge \frac{n}{k+1}$. Why?

(Here $a(G)$ is the independence number).

edited Sep 26 2010 at 6:24

Pietro Majer
19.7k●1●24●69

asked Sep 26 2010 at 5:56

Arash
27●2

1

Since you're asking, who has set you the question, or where have you come across it? How much graph theory have you already studied or worked on? – Yemon Choi Sep 26 2010 at 6:10

3

Dear Arash, I took the liberty of editing your post and changing the title (excuse me for this). You can edit and check how the TeX format works. Also note details as capital letters etc. Lastly, a precise title addressing to the question is superior to vague titles like "A maths question" &c. – Pietro Majer Sep 26 2010 at 6:28

2

Have you checked Bollobás' Extremal Graph Theory ? – Pietro Majer Sep 26 2010 at 6:36

One should hope that in this case we have $k \ge 0$ too! – drvitek Sep 26 2010 at 19:30

Gjergji Zaimi · Answer 1 · 2010-09-26 07:29:03Z UTC

7

This is also known as Turan's theorem.

answered Sep 26 2010 at 7:29

Gjergji Zaimi
37.5k●2●72●149

Arash · Accepted Answer · 2010-09-28 05:47:03Z UTC

0

by turan theorem, that is very simple:

a(G)=w(G')≥n^2/(n^2-2(n(n-1)/2-m))=n^2/(2m+n)

answered Sep 28 2010 at 5:47

Arash
27●2

4

This seems to be exactly what Gjergji Zaimi has said in his answer – Yemon Choi Sep 28 2010 at 8:36

Bounds on the independence number of a graph

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.