The total traceable number of a graph

Abstract

For a connected graph G of order n > 2 and a linear ordering s: ν_i,ν₂,...,ν_n of vertices of G, d(s) =∑ ^n-1 ₌₁, where d(ν_i, ν_i+1) is the distance between V_i and ν_i+1. The traceable number t(ν) 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 vertices of G whose first term is v. The total traceable number tt(G) of a connected graph G is defined by tt(G) = ∑ _νεV(G)^t(ν). For a nontrivial connected graph G of order n > 3, it is known that n(n - 1) ≤ tt(G) ≤ n(n - 1) + (n ² - 3n + 1). In this work,we determine all pairs n, a of positive integers that are realizable as the order and total traceable number, respectively, of some connected graph.