Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles

DOI10.5614/EJGTA.2016.4.1.3MaRDI QIDQ5006572zbMATH OpenOpenAlexFDO

Authors Michael Haythorpe

Publication date 16 August 2021

Published in Electronic Journal of Graph Theory and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution-ShareAlike 4.0 International

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

zbMATH Keywords

broken crowngraph constructionHamiltonian cycles

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Abstract: A constructive method is provided that outputs a directed graph which is named a broken crown graph, containing $5n-9$ vertices and $k$ Hamiltonian cycles for any choice of integers $ngeqkgeq4$. The construction is not designed to be minimal in any sense, but rather to ensure that the graphs produced remain non-trivial instances of the Hamiltonian cycle problem even when $k$ is chosen to be much smaller than $n$.

Recommendations

• On the minimum number of Hamiltonian cycles in regular graphs
• On Hamiltonian cycles in C_nXC_m-S_k
• scientific article; zbMATH DE number 1156588
• Constructing dense graphs with unique Hamiltonian cycles
• The maximum number of Hamiltonian cycles in graphs with a fixed number of vertices and edges

Cites work

• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Deterministic ``snakes and ladders heuristic for the Hamiltonian cycle problem
• Graphs with exactly one hamiltonian circuit
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)

Cited in

(4)

• Construction of Barnette graphs whose large subgraphs are non-Hamiltonian
• Change ringing and Hamiltonian cycles: the search for Erin and Stedman triples
• Reducing the generalised Sudoku problem to the Hamiltonian cycle problem
• Lower bounds for the algebraic connectivity of graphs with specified subgraphs

Describes a project that uses

Uses Software

• Concorde
• LKH

This page was built for publication: Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles

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