An Extension of Turán's Theorem, Uniqueness and Stability
Keywords: graph theory, Turan's Theorem
AbstractWe determine the maximum number of edges of an $n$-vertex graph $G$ with the property that none of its $r$-cliques intersects a fixed set $M\subset V(G)$. For $(r-1)|M|\ge n$, the $(r-1)$-partite Turán graph turns out to be the unique extremal graph. For $(r-1)|M|<n$, there is a whole family of extremal graphs, which we describe explicitly. In addition we provide corresponding stability results.