On maximum cycle-distributed graphs (Q1108290)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On maximum cycle-distributed graphs
scientific article

    Statements

    On maximum cycle-distributed graphs (English)
    0 references
    0 references
    1988
    0 references
    In 1975, Erdős posed the following question: Let f(n) denote the maximum number of edges in a graph on n vertices in which no two cycles have the same length. (Here loops and multiple edges are allowed.) In this paper the authors determine a bound on f(n). Theorem: For every integer \(n\geq 3\), \[ f(n)\quad \geq \quad n\quad +\quad \{(Bn-23)^{1/2}\quad +\quad 1\}/2. \] The authors conjecture that the bound given in the theorem is, in fact, the exact value of f(n), and prove this conjecture for \(3\leq n\leq 17\).
    0 references
    no two cycles of the same length
    0 references
    maximum number of edges
    0 references
    0 references
    0 references

    Identifiers