Counterexamples to a conjecture of Erdős, Pach, Pollack and Tuza
\textit{P. Erdős} et al. [ibid. 47, No. 1, 73--79 (1989; Zbl 0686.05029)] conjectured that the diameter of a \(K_{2r}\)-free connected graph of order \(n\) and minimum degree \(\delta\geq 2\) is at most \(\frac{2n(r-1)(3r+2)}{(2r^2-1)\delta}+O(1)\) for every \(r\geq 2\) where \(\delta\) is a multiple of \((r-1)(3r+2)\). In this paper, as counterexamples to the above conjecture, a class of \(K_{2r}\)-free graphs are constructed with minimum degree \(\delta\) and diameter \(\frac{(6r-5)n}{(2r-1)\delta+2r-3}+O(1)\) for \(r>1\) and \(\delta>2(r-1)(3r+2)(2r-3)\).
scientific article; zbMATH DE number 7396129