## The independence number of dense graphs with large odd girth.(English)Zbl 0811.05032

Electron. J. Comb. 2, Note N2, 3 p. (1995); printed version J. Comb. 2, 427-429 (1995).
Summary: Let $$G$$ be a graph with $$n$$ vertices and odd girth $$2k + 3$$. Let the degree of a vertex $$v$$ of $$G$$ be $$d_ 1 (v)$$. Let $$\alpha (G)$$ be the independence number of $$G$$. Then we show $\alpha(G) \geq 2^{-\left( \frac {k-1}{k} \right)} \left[\displaystyle {\sum_{v \in G}}d_ 1 (v)^{\frac{1}{k - 1}} \right]^{(k - 1)/k}.$ This improves and simplifies results proven by Denley.

### MSC:

 05C35 Extremal problems in graph theory

### Keywords:

dense graphs; odd girth; independence number
Full Text: