For a connected graph G of order n > 2 and a linear ordering s : v1, v2, . . . , vn of vertices of G, d(s) = ∑ nP−1 i=1 d(vi , vi+1), where d(vi , vi+1) is the distance between vi and vi+1. The upper traceable number t +(G) of G is t +(G) = max{d(s)}, where the maximum is taken over all linear orderings s of vertices of G. It is known that if T is a tree of order n ≥ 3, then 2n−3 ≤ t +(T) ≤ ⌊n 2 /2⌋−1 and t +(T) ≤ ⌊n 2 /2⌋−3 if T ≠ Pn. All pairs n, k for which there exists a tree T of order n and t +(T) = k are determined and a characterization of all those trees of order n ≥ 4 with upper traceable number ⌊n 2 /2⌋ − 3 is established. For a connected graph G of order n ≥ 3, it is known that n − 1 ≤ t +(G) ≤ ⌊n 2 /2⌋ − 1. We investigate the problem of determining possible pairs n, k of positive integers that are realizable as the order and upper traceable number of some connected graph.
For a nontrivial connected graph $G$ of order $n$ and a linear ordering $s\: v_1, v_2, \ldots , v_n$ of vertices of $G$, define $d(s) = \sum _{i=1}^{n-1} d(v_i, v_{i+1})$. The traceable number $t(G)$ of a graph $G$ is $t(G) = \min \lbrace d(s)\rbrace $ and the upper traceable number $t^+(G)$ of $G$ is $t^+(G) = \max \lbrace d(s)\rbrace ,$ 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.