Books in graphs-英文文献.pdfVIP

4 Books in graphs 0 0 2 B´ela Bollob´as∗†‡ and Vladimir Nikiforov† y a February 8, 2008 M 5 ] Abstract O A set of q triangles sharing a common edge is called a book of size q. C We write β (n, m) for the the maximal q such that every graph G (n, m) . contains a book of size q. In this note h 1) we compute β n, cn2 for infinitely many values of c with 1/4 t a c 1/3, 2) we show that if m ≥ (1/4 − α) n2 with 0 α 17−3 , and G has no m [ book of size at least 1/6 − 2α1/3 n then G contains an induced bipartite 1 graph G1 of order at least 1 − α1/3 n and minimal degree v 0 δ (G ) ≥ 1 − 4α1/3 n, 8 1 2 0 5 3) we apply the latter result to answer two questions of Erd˝os con- 0 2 4 cerning the booksize of graphs G n, n /4 − f (n) n every edge of which 0 is contained in a triangle, and 0 f (n) n2/5−ε . / h t 1 Introduction a m : Our notation and terminology are standard (see, e.g., [2]). Thus, G (n, m) is a v graph of order n and size m; for a graph G and a vertex u ∈ V (G) we write i X Γ (u)