An Elementary Method of Determining Hamiltonian Paths in Oriented Graphs that Admit Circuits
Jul 05, 2025
About this article
Published Online: Jul 05, 2025
Page range: 31 - 36
DOI: https://doi.org/10.2478/kbo-2025-0076
Keywords
© 2025 Vasile Căruţaşu, published by Sciendo
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.
Determining Hamiltonian paths in oriented graphs that do not support circuits is a simple matter. However, to determine Hamiltonian paths in oriented graphs that admit circuits, things are more complicated. One approach in this regard is the Ford-Fulkerson method, which proves ineffective when we have only one equivalence class, and the only method that generally works is the Latin matrix method in which the concatenation operation is used. In this study, another way of determining the Hamiltonian paths is proposed, which is based on elementary operations and which uses, with certain limitations, the operations from Y. Chen’s algorithm for the transition from the capacitive connected matrix to the paths matrix.