An extension of Turán's theorem, uniqueness and stability
Allen, P.
, Böttcher, J., Hladký, J. & Piguet, D.
(2014).
An extension of Turán's theorem, uniqueness and stability.
Electronic Journal of Combinatorics,
21(4), P4.5.
, Böttcher, J., Hladký, J. & Piguet, D.
(2014).
An extension of Turán's theorem, uniqueness and stability.
Electronic Journal of Combinatorics,
21(4), P4.5.
We 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⊂V(G) . For (r−1)|M|≥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.