Premium
An extremal problem on K r ‐free graphs
Author(s) -
Frankl Peter,
Pach János
Publication year - 1988
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190120407
Subject(s) - combinatorics , mathematics , graph , upper and lower bounds , constant (computer programming) , discrete mathematics , mathematical analysis , computer science , programming language
Let r, t ⩾ 2 be integers and c a constant, 0 < c ⩽ ( r ‐ 2)/( r − 1). Suppose that G is a K r ‐free graph on n vertices in which any t distinct vertices have at most cn common neighbors. Here an asymptotically best bound is obtained for the maximal number of edges in such graphs. This solves a problem of Babai et al. in a more general form.