Turán theorems with repeated degrees (Q1198646)
From MaRDI portal
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