The upper traceable number of a graph

Abstract

For a nontrivial connected graph G of order n and a linear ordering s: v1, v2,...,vn of vertices of G, define d(s) = ∑i=1n-1d(vi,vi+1). The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t+(G) of G is t+(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t+(G) - t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. © 2008 Mathematical Institute, Academy of Sciences of Czech Republic.