On maximum cycle-distributed graphs
type: Item
instance of: scholarly article
title: On maximum cycle-distributed graphs
zbMATH Open document ID: 0654.05048
DOI: 10.1016/0012-365X(88)90030-1
author: Yongbing Shi
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4066939
zbMATH Keywords: no two cycles of the same length
zbMATH Keywords: maximum number of edges
MaRDI profile type: Publication
cites work: Q5422499
cites work: Q4294627
full work available at URL: 0012-365x(88)90030-1
OpenAlex ID: W1981416130
description: scientific article; zbMATH DE number 4066939