# zbMATH — the first resource for mathematics

Bounds of lengths of open Hamiltonian walks. (English) Zbl 0782.05056
An open sequence of edges passing through each vertex of a connected graph is called an open walk and any open walk of minimal length is called an open Hamiltonian walk. Denote by $$l_ G$$ the length of open Hamiltonian walks in the graph $$G$$. It is proved that if $$k$$ is the minimal number of edges which we have to add to a connected graph $$G_ 1$$ of order $$n\geq 4$$ to obtain a graph containing a Hamiltonian path $$(k\leq n-3)$$, then $$l_{G_ 1}\leq 2(n-1)-{n+k-1\over k+1}$$. It is also shown that if $$G$$ is obtained from $$G_ 1$$ by omitting a unique edge, then $$l_ G\leq {2l_ G+1\over 3}$$.
Reviewer: H.Li (Orsay)

##### MSC:
 05C45 Eulerian and Hamiltonian graphs
Full Text: