On maximum cycle-distributed graphs

DOI10.1016/0012-365X(88)90030-1MaRDI QIDQ1108290zbMATH OpenOpenAlexFDO

Authors Yongbing Shi

Publication date 1988

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(88)90030-1

zbMATH Keywords

maximum number of edgesno two cycles of the same length

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

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\).

Recommendations

• scientific article; zbMATH DE number 1151856
• An old problem of Erdős: a graph without two cycles of the same length
• On the size of graphs with all cycles having distinct length
• On the number of edges in some graphs
• A lower bound for the number of edges in a graph containing no two cycles of the same length

Cites work

• Graph theory
• scientific article; zbMATH DE number 568835 (Why is no real title available?)

Cited in

(19)

• The maximum number of cycles in the complement of a tree
• Maximal cycles in graphs
• The number of edges in a maximum cycle-distributed graph
• On the size of graphs with all cycles having distinct length
• On simple MCD graphs containing a subgraph homeomorphic to \(K_ 4\)
• Covering non-uniform hypergraphs
• (2)-pancyclic graphs
• Non-repeated cycle lengths and Sidon sequences
• Spectral radius, edge-disjoint cycles and cycles of the same length
• On the number of edges in some graphs
• On the size of graphs without repeated cycle lengths
• The edge numbers of a class of graphs
• Some open problems on cycles
• scientific article; zbMATH DE number 1151856 (Why is no real title available?)
• scientific article; zbMATH DE number 1933072 (Why is no real title available?)
• Nested cycles with no geometric crossings
• On absorbing cycles in min-max digraphs
• An old problem of Erdős: a graph without two cycles of the same length
• On the number of sets of cycle lengths

This page was built for publication: On maximum cycle-distributed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108290)