On open Hamiltonian walks in graphs. (English) Zbl 0758.05067

Vacek, Pavel

Arch. Math., Brno 27a, 105-111 (1991).

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.

MSC:

05C45

Eulerian and Hamiltonian graphs

Keywords:

Hamiltonian graph; Hamiltonian path; Hamiltonian walk; open Hamiltonian walk; cactus