Title of article :
Books in graphs
Author/Authors :
Bollobلs، نويسنده , , Béla and Nikiforov، نويسنده , , Vladimir، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2005
Pages :
12
From page :
259
To page :
270
Abstract :
A set of q triangles sharing a common edge is called a book of size q. We write β(n,m) for the maximal q such that every graph G(n,m) contains a book of size q. In this note compute β(n,cn2) for infinitely many values of c with 1/4<c<1/3, show that if m≥(1/4−α)n2 with 0<α<17−3, and G has no book of size at least (1/6−2α1/3)n then G contains an induced bipartite graph G1 of order at least (1−α1/3)n and minimal degreeδ(G1)≥12−4α1/3n, apply the latter result to answer two questions of Erdős concerning the booksize of graphs G(n,n2/4−f(n)n) every edge of which is contained in a triangle, and 0<f(n)<n2/5−ε.
Journal title :
European Journal of Combinatorics
Serial Year :
2005
Journal title :
European Journal of Combinatorics
Record number :
1546991
Link To Document :
بازگشت