Edge maximal non-bipartite graphs without odd cycles of prescribed lengths (Q1348667): Difference between revisions

Main result of the paper is that non-bipartite graphs on \(n\) vertices having no odd cycle of length \(\leq 2k+1\) have at most \(\lfloor{1\over 4}(n- 2k+1)^2\rfloor+ 2k-1\) edges. The extremal graphs achieving this bound are characterized. For odd \(n\) among these extremal graphs are Hamiltonian ones, while for even \(n\) the sharp upper bound on the number \(e(G)\) of edges of Hamiltonian, non-bipartite graphs on \(n\) vertices having no odd cycle of length \(\leq 2k+1\) is \({1\over 4}(n-8k+8)+ 4k^2- 7\), the extremal graphs being also characterized.