Counterexamples to a conjecture of Erdős, Pach, Pollack and Tuza (Q1984510)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Counterexamples to a conjecture of Erdős, Pach, Pollack and Tuza |
scientific article |
Statements
Counterexamples to a conjecture of Erdős, Pach, Pollack and Tuza (English)
0 references
16 September 2021
0 references
\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)\).
0 references
diameter
0 references
minimum degree
0 references