On reduced Hamilton walksMalnič, Aleksander (Avtor) Požar, Rok (Avtor) algorithmHamilton walknonstandard metricreduced walkA Hamilton walk in a finite graph is a walk, either open or closed, that traverses every vertex at least once. Here, we introduce Hamilton walks that are reduced in the sense that they avoid immediate backtracking: a reduced Hamilton walk never traverses the same edge forth and back consecutively. While every connected graph admits a Hamilton walk, existence of a reduced Hamilton walk is not guaranteed for all graphs. However, we prove that a reduced Hamilton walk does exist in a connected graph with minimal valency at least 2. Furthermore, given such a graph on n vertices, we present an O(n2)-time algorithm that constructs a reduced Hamilton walk of length at most n(n+3)/2. Specifically, for a graph belonging to a family of regular expander graphs, we can find a reduced Hamilton walk of length at most c(6n−2)logn+2n, where c is a constant independent of n.20262025-09-09 12:40:17Članek v reviji21698UDK: 51ISSN pri članku: 0096-3003DOI: 10.1016/j.amc.2025.129695COBISS.SI-ID: 248238083sl