An Extension of Turán's Theorem, Uniqueness and Stability
Copyright policy )An Extension of Turán's Theorem, Uniqueness and Stability
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\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.
- Západočeská univerzita v Plzni (University of West Bohemia in Pilsen) Czech Republic
- London School of Economics and Political Science United Kingdom
- University of West Bohemia Czech Republic
- Czech Academy of Sciences Czech Republic
- University of Warwick
Extremal problems in graph theory, Turán's theorem, graph theory, Turan's theorem, extremal graph theory, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO)
Extremal problems in graph theory, Turán's theorem, graph theory, Turan's theorem, extremal graph theory, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!