A Note on Vertex-Covering Walks

Abstract

For a nontrivial connected graph $G$ of order $n$ and a cyclic ordering $s:v_1,v_2,\dots ,v_n,v_{n+1}=v_1$ of $V(G)$, let $d(s)=\sum _{i=1}^{n}d(v_i,v_{i+1})$, where $d(v_i,v_{i+1})$ is the distance between $v_i$ and $v_{i+1}$ for $1\le i\le n$. The Hamiltonian number $h(G)$ and the upper Hamiltonian number $h^{+}(G)$ of $G$ are defined as:

1. $h(G)=min\{d(s)\}$, where the minimum is taken over all cyclic orderings $s$ of $V(G)$.
2. $h^{+}(G)=max\{d(s)\}$, where the maximum is taken over all cyclic orderings $s$ of $V(G)$.

All connected graphs $G$ with $h^{+}(G)=h(G)$ and $h^{+}(G)=h(G)+1$ have been characterized in [6, 13]. In this note, we first present a new and significantly improved proof of the characterization of all graphs whose Hamiltonian and upper Hamiltonian numbers differ by 1. We then determine all pairs of integers that can be realized as the order and upper Hamiltonian number of some tree.