An extension of Turan's Theorem, uniqueness and stability

Autor(es)

Allen, Peter ^[1] ; Boettcher, Julia ^[1] ; Hladky, Jan ^[2] ; Piguet, Diana ^[3]

Afiliação do(s) autor(es)

^[1] London Sch Econ, Dept Math, London WC2A 2AE - England

^[2] Acad Sci Czech Republic, Math Inst, Prague - Czech Republic

^[3] Univ W Bohemia, European Ctr Excellence NTIS, Plzen 30614 - Czech Republic

• Tipo de documento: Artigo Científico
• Fonte: ELECTRONIC JOURNAL OF COMBINATORICS; v. 21, n. 4 OCT 2 2014.
• Citações Web of Science: 1

Resumo

We determine the maximum number of edges of an n-vertex graph G with h the property that none of its e-cliques intersects a fixed set M subset of V(G). For (r-1)vertical bar M vertical bar >= n, the (r-1)-partite Turn graph turns out to be the unique extremal graph. For (r-1)vertical bar M vertical bar < n, there is a whole family of extremal graphs, which we describe explicitly. In addition we provide corresponding stability results. (AU)

• Processo FAPESP: 09/17831-7 - Problemas de imersão e empacotamento em teoria extremal dos grafos
• Beneficiário: Julia Boettcher
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 10/09555-7 - Problemas estruturais, probabilísticos e de imersão em teoria extremal dos grafos
• Beneficiário: Peter David Allen
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado