On reduced Hamilton walks

Malnič, Aleksander (author), Požar, Rok (author)

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$.

• Language: English
• Keywords: algorithm, Hamilton walk, nonstandard metric, reduced walk
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: PEF - Faculty of Education
• Publication status: Published
• Publication version: Version of Record
• Year: 2026
• Number of pages: 11 str.
• Numbering: Vol. 510, art. 129695
• PID: 20.500.12556/RUL-182657
• UDC: 519.17
• ISSN on article: 0096-3003
• DOI: 10.1016/j.amc.2025.129695
• COBISS.SI-ID: 248238083
• Publication date in RUL: 20.05.2026

Record is a part of a journal

• Title: Applied mathematics and computation
• Shortened title: Appl. math. comput.
• Publisher: Elsevier
• ISSN: 0096-3003
• COBISS.SI-ID: 24983808

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: algoritem, hamiltonski sprehod, nestandardna metrika, reduciran sprehod