20.500.12556/DiRROS-23757 On reduced Hamilton walks A 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(n^2)$-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)\log n+2n$, where $c$ is a constant independent of $n$. algorithm Hamilton walk nonstandard metric reduced walk algoritem hamiltonski sprehod nestandardna metrika reduciran sprehod true false true Angleški jezik Slovenski jezik Neznano 2025-10-01 09:15:23 2025-10-01 09:15:23 2025-10-24 03:54:58 0000-00-00 00:00:00 2026 0 0 str. 1-11 art. 129695 Vol. 510 1 Feb. 2026 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2026-02-01 519.17 0096-3003 10.1016/j.amc.2025.129695 248238083 1-s2.0-S0096300325004217-main.pdf 1-s2.0-S0096300325004217-main.pdf 1 FBE5B262667B45FEB56A4CE21367B6BC fde047d052f4781953e95538b7275dcb8c103c2b057bae4caaf7b3dd5c287763 292de4c2-9e97-11f0-9bb7-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=35216 https://www.sciencedirect.com/science/article/pii/S0096300325004217 1 66c438fc-9e96-11f0-9bb7-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=35215 Inštitut za matematiko, fiziko in mehaniko 0 0 0