Some relatively sparse graphs with Hamiltonian cycles

Citation

Recaman B, Rowlinson P & Yang Y (1993) Some relatively sparse graphs with Hamiltonian cycles. Publikacije Elektrotehnickog fakulteta – Serija: Matematika, (4), pp. 99-100. http://pefmath2.etf.rs/files/113/807.pdf

Abstract
The graph Gk(n) has vertices 1,2,…,n, and edges the pairs {a, b} for which a + b is a kth power. Computer evidence is presented in support of the conjecture that for each k, Gk(n) is Hamiltonian for large enough n.

Keywords
relatively sparse graphs; Hamiltonian cycles

Journal
Publikacije Elektrotehnickog fakulteta – Serija: Matematika, Issue 4