The independence number of graphs with large odd girth (Q1346728)

Summary: Let \(G\) be an \(r\)-regular graph of order \(n\) and independence number \(\alpha(G)\). We show that if \(G\) has odd girth \(2k+ 3\) then \(\alpha(G)\geq n^{1-1/k} r^{1/k}\). We also prove similar results for graphs which are not regular. Using these results we improve on the lower bound of Monien and Speckenmeyer, for the independence number of a graph of order \(n\) and odd girth \(2k+ 3\).