Paths through equally spaced points on a circle

zbMATH Open1502.05107arXiv2205.06004MaRDI QIDQ5043574FDOQ5043574

Authors: Brendan D. McKay, Tim Peters 

Publication date: 6 October 2022

Abstract: Consider $n$ points evenly spaced on a circle, and a path of $n-1$ chords that uses each point once. There are $m=lfloorn/2floor$ possible chord lengths, so the path defines a multiset of $n-1$ elements drawn from $1,2,ldots,m$. The first problem we consider is to characterize the multisets which are realized by some path. Buratti conjectured that all multisets can be realized when $n$ is prime, and a generalized conjecture for all $n$ was proposed by Horak and Rosa. Previously the conjecture was proved for $nleq19$ and $n=23$; we extend this to $nleq37$ (OEIS sequence A352568). The second problem is to determine the number of distinct (euclidean) path lengths that can be realized. For this there is no conjecture; we extend current knowledge from $nleq16$ to $nleq37$ (OEIS sequence A030077). When $n$ is prime, twice a prime, or a power of 2, we prove that two paths have the same length only if they have the same multiset of chord lengths.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On Hamiltonian paths with prescribed edge lengths in the complete graph
• Hamiltonian paths in the complete graph with edge-lengths 1, 2, 3
• A new result on the problem of Buratti, Horak and Rosa
• Growable realizations: a powerful approach to the Buratti-Horak-Rosa conjecture
• New methods to attack the Buratti-Horak-Rosa conjecture

zbMATH Keywords

Hamiltonian pathpoints on a circleBuratti-Horak-Rosa conjecture

Mathematics Subject Classification ID

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

Cites Work

• On a problem of Marco Buratti
• Hamiltonian paths in the complete graph with edge-lengths 1, 2, 3
• A new result on the problem of Buratti, Horak and Rosa
• On the Buratti-Horak-Rosa conjecture about Hamiltonian paths in complete graphs
• New methods to attack the Buratti-Horak-Rosa conjecture
• A note on the Buratti-Horak-Rosa conjecture about Hamiltonian paths in complete graphs
• Growable realizations: a powerful approach to the Buratti-Horak-Rosa conjecture

Cited In (2)

• Separating path systems for the complete graph
• Counting paths between points on a circle.

Uses Software

• OEIS

This page was built for publication: Paths through equally spaced points on a circle

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