Edge maximal non-bipartite graphs without odd cycles of prescribed lengths (Q1348667)

From MaRDI portal
Revision as of 10:36, 20 February 2024 by RedirectionBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
Edge maximal non-bipartite graphs without odd cycles of prescribed lengths
scientific article

    Statements

    Edge maximal non-bipartite graphs without odd cycles of prescribed lengths (English)
    0 references
    0 references
    0 references
    14 May 2002
    0 references
    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.
    0 references
    Hamiltonian graphs
    0 references
    odd cycle
    0 references
    extremal graphs
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references