Paths through equally spaced points on a circle

MaRDI QIDQ5043574zbMATH OpenFDO

Authors Brendan D. McKay, Tim Peters

Publication date 6 October 2022

Full work available at URL https://arxiv.org/abs/2205.06004, https://cs.uwaterloo.ca/journals/JIS/VOL25/McKay/mckay2.html

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

zbMATH Keywords

Buratti-Horak-Rosa conjectureHamiltonian pathpoints on a circle

Mathematics Subject Classification ID

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

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.

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

Cites work

• A new result on the problem of Buratti, Horak and Rosa
• 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
• Hamiltonian paths in the complete graph with edge-lengths 1, 2, 3
• New methods to attack the Buratti-Horak-Rosa conjecture
• On a problem of Marco Buratti
• On the Buratti-Horak-Rosa conjecture about Hamiltonian paths in complete graphs

Cited in

(3)

• Separating path systems for the complete graph
• Counting paths between points on a circle.
• Circulant TSP: vertices of the edge-length polytope and superpolynomial lower bounds

Describes a project that uses

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)