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.
- Turán's theorem and maximal degrees
- A note on repeated degrees of line graphs
- Singular Turán numbers and worm-colorings
- Ramsey numbers for degree monotone paths
- scientific article; zbMATH DE number 140115 (Why is no real title available?)
- Forcing k-repetitions in degree sequences
- scientific article; zbMATH DE number 1062586 (Why is no real title available?)
- scientific article; zbMATH DE number 1484577 (Why is no real title available?)
- People Who Know People
- scientific article; zbMATH DE number 810044 (Why is no real title available?)
- Extremal graph theoretic questions for q-ary vectors
This page was built for publication: Turán theorems with repeated degrees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198646)
