Hamiltonian Spectra of Trees

Abstract

Let \(G\) be a connected graph, and let \(d(u,v)\) denote the distance between vertices \(u\) and \(v\) in \(G\). For any cyclic ordering \(\pi\) of \(V(G)\), let \(\pi = (v_1, v_2, \ldots, v_n, v_{n+1} = v_1)\), and let \(d(\pi) = \sum\limits_{i=1}^n d(v_i, v_{i+1})\). The set of possible values of \(d(\pi)\) of all cyclic orderings \(\pi\) of \(V(G)\) is called the Hamiltonian spectrum of \(G\). We determine the Hamiltonian spectrum for any tree.