zbMATH — the first resource for mathematics

On open Hamiltonian walks in graphs. (English) Zbl 0758.05067
Summary: If \(G\) is a graph of order \(n\), an open Hamiltonian walk is meant any open sequence of edges of minimal length which includes every vertex of \(G\). Clearly, the length of such an open walk is at least \(n-1\), and is equal to \(n-1\) if and only if \(G\) contains a Hamiltonian path. In this paper, basic properties of open Hamiltonian walks and upper bounds of their lengths in some classes of graphs are studied.

05C45 Eulerian and Hamiltonian graphs
PDF BibTeX Cite
Full Text: EuDML