Non-repeated cycle lengths and Sidon sequences

DOI10.1007/S11856-021-2222-1zbMATH Open1487.05129OpenAlexW3209855320MaRDI QIDQ2130516FDOQ2130516

Authors Jie Ma, Tianchi Yang

Publication date 25 April 2022

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.12513

zbMATH Keywords

maximum number of edges2-connected graph without repeated cycle lengths

Mathematics Subject Classification ID

Distance in graphs (05C12) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Abstract: We prove a conjecture of Boros, Caro, F"uredi and Yuster on the maximum number of edges in a 2-connected graph without repeated cycle lengths, which is a restricted version of a longstanding problem of ErdH{o}s. Our proof together with the matched lower bound construction of Boros, Caro, F"uredi and Yuster show that this problem can be conceptually reduced to the seminal problem of finding the maximum Sidon sequences in number theory.

Recommendations

• Note on graphs without repeated cycle lengths
• On the size of graphs without repeated cycle lengths
• scientific article; zbMATH DE number 1933072
• An old problem of Erdős: a graph without two cycles of the same length
• On maximum cycle-distributed graphs

Cites work

• A note on uniquely pancyclic graphs
• An inequality for B2-sequences
• Covering non-uniform hypergraphs
• Graph theory with applications
• Note on graphs without repeated cycle lengths
• On a Problem of Sidon in Additive Number Theory, and on some Related Problems
• On maximum cycle-distributed graphs
• On the number of edges in some graphs

Cited in

(4)

• An old problem of Erdős: a graph without two cycles of the same length
• Random Sidon sequences
• Spectral radius, edge-disjoint cycles and cycles of the same length
• No cubic integer polynomial generates a Sidon sequence

This page was built for publication: Non-repeated cycle lengths and Sidon sequences

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