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)


05C45 Eulerian and Hamiltonian graphs
Full Text: EuDML EMIS