6533b857fe1ef96bd12b4cd7

RESEARCH PRODUCT

ℓ-distant Hamiltonian walks in Cartesian product graphs

Olivier Togni

subject

CombinatoricsGray codeDiscrete mathematicssymbols.namesakeApplied MathematicssymbolsDiscrete Mathematics and CombinatoricsCartesian productHamiltonian pathGraphHypercube graphMathematicsHamiltonian path problem

description

Abstract We introduce and study a generalisation of Hamiltonian cycles: an l-distant Hamiltonian walk in a graph G of order n is a cyclic ordering of its vertices in which consecutive vertices are at distance l. Conditions for a Cartesian product graph to possess such an l-distant Hamiltonian walk are given and more specific results are presented concerning toroidal grids.

https://doi.org/10.1016/j.endm.2009.07.012