The independence number of dense graphs with large odd girth (Q1344960): Difference between revisions

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.