Turán theorems with repeated degrees
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.
scientific article; zbMATH DE number 90261