Non-repeated cycle lengths and Sidon sequences

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

Jie Ma, Tianchi Yang

Publication date: 25 April 2022

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

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.

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)

Cites Work

• Title not available (Why is that?)
• On a Problem of Sidon in Additive Number Theory, and on some Related Problems
• An inequality for B2-sequences
• On maximum cycle-distributed graphs
• Covering non-uniform hypergraphs
• On the number of edges in some graphs
• Note on graphs without repeated cycle lengths
• Title not available (Why is that?)

Cited In (4)

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

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)