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 \((r-1)(3r+2)\), then the diameter of \(G\), denoted by \(D(G)\), satisfies \[ D(G) \leq \frac{2(r-1)(3r+2)}{(2r^2-1)\delta}n +O(1) \] as \(n\) approaches infinity. If \(G\) is \(K_{2r+1}\)-free and \(\delta\) is a multiple of \(3r-1\), then show that \[ D(G) \leq \frac{3r-1}{r\delta}n + O(1) \] as \(n\) approaches infinity.In [1], bounds for the diameters of triangle-free 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), 73-79.
|