20.500.12556/RUP-21698 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(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. algorithm Hamilton walk nonstandard metric reduced walk algoritem hamiltonski sprehod nestandardna metrika reduciran sprehod true false true Angleški jezik Slovenski jezik Članek v reviji 2025-09-09 12:40:17 2025-09-09 12:40:18 2025-09-27 03:02:10 0000-00-00 00:00:00 2026 0 0 str. 1-11 art. 129695 Vol. 510 1 Feb. 2026 0000-00-00 Zaloznikova NiDoloceno NiDoloceno 0000-00-00 0000-00-00 2025-09-02 51 0096-3003 10.1016/j.amc.2025.129695 248238083 RAZ_Malnic_Aleksander_2026.pdf RAZ_Malnic_Aleksander_2026.pdf 1 66FADE9EBCDF55DD76090DB30C0614BF 19fa061ff910c8818cc37ec6168f872cf9916d143b7f70c7baf209fe3f395f7e 9fb3814a-8d69-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=31521 https://www.sciencedirect.com/science/article/pii/S0096300325004217 1 772e0193-8d69-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=31520 Fakulteta za matematiko, naravoslovje in informacijske tehnologije Inštitut Andrej Marušič 0 0 0