Laceable knights

Michael Dupuis, Stan Wagon

Abstract


A bipartite graph is Hamilton-laceable if for any two vertices in different parts there is a Hamiltonian path from one to the other. Using two main ideas (an algorithm for finding Hamiltonian paths and a decomposition lemma to move from smaller cases to larger) we show that the graph of knight’s moves on an m × n board is Hamilton-laceable iff m ≥ 6, n ≥ 6, and one of m, n is even. We show how the algorithm leads to new conjectures about Hamiltonian paths for various families, such as generalized Petersen graphs, I-graphs, and cubic symmetric graphs.


Keywords


Hamilton-laceable, generalized Petersen graphs, Hamilton-connected, Hamiltonian paths, knight graph, traceable

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.420.3c5

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications