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.


05C35 Extremal problems in graph theory
Full Text: EuDML EMIS