A note on the number of edges in a Hamiltonian graph with no repeated cycle length

MaRDI QIDQ4595658zbMATH OpenFDO

Authors Joey Lee, Craig Timmons

Publication date 6 December 2017

Full work available at URL https://arxiv.org/abs/1705.07545, http://ajc.maths.uq.edu.au/pdf/69/ajc_v69_p286.pdf

zbMATH Keywords

maximum number of edges

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Distance in graphs (05C12) Paths and cycles (05C38)

Abstract: Let $G$ be an $n$-vertex graph obtained by adding chords to a cycle of length $n$. Markstr"{o}m asked for the maximum number of edges in $G$ if there are no two cycles in $G$ with the same length. A simple counting argument shows that such a graph can have at most $n+sqrt2n+1$ edges. Using difference sets in $mathbb{Z}_n$, we show that for infinitely many $n$, there is an $n$-vertex Hamiltonian graph with $n+sqrtn-3/4-3/2$ edges and no repeated cycle length.

Recommendations

• Note on graphs without repeated cycle lengths
• scientific article; zbMATH DE number 1933072
• On the size of graphs without repeated cycle lengths
• Cycle spectra of Hamiltonian graphs
• scientific article; zbMATH DE number 1824729

Cited in

(1)

• An old problem of Erdős: a graph without two cycles of the same length

This page was built for publication: A note on the number of edges in a Hamiltonian graph with no repeated cycle length

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