On the size of graphs with all cycles having distinct length
type: Item
instance of: scholarly article
title: On the size of graphs with all cycles having distinct length
zbMATH Open document ID: 0790.05046
DOI: 10.1016/0012-365X(93)90311-G
author: Chunhui Lai
published in: Discrete Mathematics
publication date: 1994-06-22T00:00:00Z
review text: By \(f(n)\) the author means the maximum number of edges in a graph of order \(n\) in which no two cycles have the same length. In the book of \textit{J. A. Bondy} and \textit{U. S. R. Murty} [Graph theory with applications (1976)] one finds Erdős' question of determining \(f(n)\). In the paper under review it is shown that if \(t\) is positive integer then \(f(n)\geq n+9t-1\) for \(n\geq 36.5t^ 2-4.5t+1\). Finally it is conjectured that \(\lim(f(n)-n)/\sqrt n\leq\sqrt 3\).
reviewed by: J.Sedláček
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 500653
zbMATH Keywords: size of graphs
zbMATH Keywords: cycles
MaRDI profile type: Publication
cites work: Q5422499
cites work: On maximum cycle-distributed graphs
description: scientific article; zbMATH DE number 500653