A Note on Bounds for the Maximum Traceable Number of a Graph

Abstract

For a connected graph \(G\) of order \(n \geq 2\) and a linear ordering \(s = v_1, v_2, \ldots, v_n\) of \(V(G)\), define \(d(s) = \sum_{i=1}^{n-1} d(v_i, v_{i+1})\), where \(d(v_i, v_{i+1})\) is the distance between \(v_i\) and \(v_{i+1}\). The traceable number \(t(G)\) and upper traceable number \(t^+(G)\) of \(G\) are defined by \(t(G) = \min\{d(s)\}\) and \(t^+(G) = \max\{d(s)\}\), respectively, where the minimum and maximum are taken over all linear orderings \(s\) of \(V(G)\). The traceable number \(t(v)\) of a vertex \(v\) in \(G\) is defined by \(t(v) = \min\{d(s)\}\), where the minimum is taken over all linear orderings \(s\) of \(V(G)\) whose first term is \(v\). The \({maximum\; traceable \;number}\) \(t^*(G)\) of \(G\) is then defined by \(t^*(G) = \max\{t(v) : v \in V(G)\}\). Therefore, \(t(G) \leq t^*(G) \leq t^+(G)\) for every nontrivial connected graph \(G\). We show that \(t^*(G) \leq \lfloor \frac{t(G)+t^+(G)+1}{2}\rfloor\) for every nontrivial connected graph \(G\) and that this bound is sharp. Furthermore, it is shown that for positive integers \(a\) and \(b\), there exists a nontrivial connected graph \(G\) with \(t(G) = a\) and \(t^*(G) = b\) if and only if \(a \leq b \leq \left\lfloor \frac{3n}{2} \right\rfloor\).