On the Length of a Shortest Spanning Walk

Abstract

A spanning walk of a graph is a walk that contains all vertices in a graph. The purpose of this article is to find number of edges of a shortest spanning walk of a connected graph G with n vertices. There are 3 cases in the scope of the study: a shortest spanning walk with respect to fixed endpoints; a shortest spanning walk with respect to a fixed initial vertex and a shortest spanning walk without any restriction.
Define w₂ (G) =   {number of edges of a shortest spanning walk with endpoints u and v where u ≠ v} ,
w₁ (G) = {number of edges of a shortest spanning walk that starts at v} ,
and w₀ (G) = number of edges of a shortest spanning walk. It is obvious that
w_i (G₁) = 0 and w_i (G₂) = 1 for i = 0,1,2 and a connected graph G_j with j = 1 or 2 vertices.
We find bounds on each parameter in which all bounds are sharp for n ≥ 3 as follows
n - 1 ≤ w₂ (G) ≤ 2n-3;
n - 1 ≤ w₁ (G) ≤ 2n-3;
n - 1 ≤ w₀ (G) ≤ 2n-4,
Moreover for each k between lower bound and upper bound of any w_i , there exists a graph G with n vertices and w_i (G) = k.