𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Extremal graphs with bounded densities of small subgraphs

✍ Scribed by Griggs, Jerrold R.; Simonovits, Mikl�os; Thomas, George Rubin

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
373 KB
Volume
29
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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án theory can be applied to such problems. The case µ = ( k 2 ) -1 is the famous result of Turán.

📜 SIMILAR VOLUMES

Decomposing large graphs with small grap
Decomposing large graphs with small graphs of high density
✍ Yuster, Raphael 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 146 KB 👁 2 views

It is shown that for every positive integer h, and for every > 0, there are graphs H = (V H , E H ) with at least h vertices and with density at least 0.5with the following property: any graph with minimum degree at least |V G | 2 (1 + o(1)) and |E H | divides |E G |, then G has an H-decomposition.

Sharp bounds for decompositions of graph
Sharp bounds for decompositions of graphs into completer-partite subgraphs
✍ Gregory, David A.; Vander Meulen, Kevin N. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 435 KB 👁 2 views

If G is a graph on n vertices and r 2 2, w e let m,(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, f(G). In determining m,(G), w e may assume that no two vertices of G have the same neighbor set. For such reduced graphs G, w

Connected subgraphs with small degree su
Connected subgraphs with small degree sums in 3-connected planar graphs
✍ Enomoto, Hikoe; Ota, Katsuhiro 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 2 views

It is well-known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3-connected planar graph has an edge xy such that deg(x) + deg(y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we sh

Berge graphs with chordless cycles of bo
Berge graphs with chordless cycles of bounded length
✍ Rusu, Irena 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB

A graph is called weakly triangulated if it contains no chordless cycle on five or more vertices (also called hole) and no complement of such a cycle (also called antihole). Equivalently, we can define weakly triangulated graphs as antihole-free graphs whose induced cycles are isomorphic either to C