Turán theorems with repeated degrees (Q1198646)

From MaRDI portal
Revision as of 02:31, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
Turán theorems with repeated degrees
scientific article

    Statements

    Turán theorems with repeated degrees (English)
    0 references
    16 January 1993
    0 references
    Let \(s_ q(n)\) denote the maximum number of edges in a graph with \(n\) vertices and no \(K_{q+1}\) in which all vertices have the same degree. This paper determines \(s_ q(n)\) asymptotically, exhibits the extremal graphs (complete multipartite graphs) in certain cases, exhibits almost extremal graphs in the remaining cases, and investigates how far the almost extremal graphs are from being extremal. The case when \(q=1\) contains all of the essentials. The work was inspired by the following result of the author. If \(G\) is any graph with at least 6 vertices, then either \(G\) or \(G^ c\) contains a \(K_ 3\) in which two vertices have the same degree.
    0 references
    Turán theorems
    0 references
    maximum number of edges
    0 references
    degree
    0 references
    extremal graphs
    0 references

    Identifiers