For a connected graph G of order n > 3 and an ordering s : v1, v2, . . . , vn of the vertices of G, d(s) = n−1 ∑ i=1 d(vi , vi+1), where d(vi , vi+1) is the distance between vi and vi+1. The traceable number t(G) of G is defined by t(G) = min {d(s)} , where the minimum is taken over all sequences s of the elements of V (G). It is shown that if G is a nontrivial connected graph of order n such that l is the length of a longest path in G and p is the maximum size of a spanning linear forest in G, then 2n−2−p ≤ t(G) ≤ 2n−2−l and both these bounds are sharp. We establish a formula for the traceable number of every tree in terms of its order and diameter. It is shown that if G is a connected graph of order n ≥ 3, then t(G) ≤ 2n − 4. We present characterizations of connected graphs of order n having traceable number 2n − 4 or 2n − 5. The relationship between the traceable number and the Hamiltonian number (the minimum length of a closed spanning walk) of a connected graph is studied. The traceable number t(v) of a vertex v in a connected graph G is defined by t(v) = min{d(s)}, where the minimum is taken over all linear orderings s of the vertices of G whose first term is v. We establish a formula for the traceable number t(v) of a vertex v in a tree. The Hamiltonian-connected number hcon(G) of a connected graph G is defined by hcon(G) = ∑ v∈V (G) t(v). We establish sharp bounds for hcon(G) of a connected graph G in terms of its order.
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.