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
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