Diameter of a \(K_r\)free graph
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
A problem on the diameter of a \(K_r\)free graph (proposed by Erdös, Pach, Pollack and Tuza [1])
Let \(G\) denote a connected graph on \(n\) vertices with minimum degree \(\delta\). Show that if \(G\) is \(K_{2r}\)free and \(\delta\) is a multiple of \((r1)(3r+2)\), then the diameter of \(G\), denoted by \(D(G)\), satisfies \[ D(G) \leq \frac{2(r1)(3r+2)}{(2r^21)\delta}n +O(1) \] as \(n\) approaches infinity. If \(G\) is \(K_{2r+1}\)free and \(\delta\) is a multiple of \(3r1\), then show that \[ D(G) \leq \frac{3r1}{r\delta}n + O(1) \] as \(n\) approaches infinity.In [1], bounds for the diameters of trianglefree or \( C_k\)free graphs with given minimum degree were derived.
Bibliography  

1 
P. Erdös, J. Pach, R. Pollack and Zs. Tuza, Radius, diameter, and
minimum degree, J. Comb. Theory Ser. B 47 (1989), 7379.
