Premium
Extremal graphs with bounded densities of small subgraphs
Author(s) -
Griggs Jerrold R.,
Simonovits Miklóos,
Thomas George Rubin
Publication year - 1998
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/(sici)1097-0118(199811)29:3<185::aid-jgt6>3.0.co;2-m
Subject(s) - combinatorics , mathematics , mathematical proof , bounded function , vertex (graph theory) , graph , discrete mathematics , simple (philosophy) , extremal graph theory , line graph , voltage graph , mathematical analysis , philosophy , geometry , epistemology
Let Ex( n , k , μ) denote the maximum number of edges of an n ‐vertex graph in which every subgraph of k vertices has at most μ edges. Here we summarize some known results of the problem of determining Ex( n , k , μ), give simple proofs, and find some new estimates and extremal graphs. Besides proving new results, one of our main aims is to show how the classical Turáan theory can be applied to such problems. The case μ = $(^{k}_{2}) - 1$ is the famous result of Turáan. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 185–207, 1998