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
    0 references
    0 references
    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
    0 references
    diameter
    0 references
    minimum degree
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references