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

Shearer, James B.

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