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

Abstract

For a connected graph $G$ of order $n\ge 2$ and a linear ordering $s=v_1,v_2,\dots ,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 $maximumtraceablenumber$ $t^{\ast }(G)$ of $G$ is then defined by $t^{\ast }(G)=max\{t(v):v\in V(G)\}$. Therefore, $t(G)\le t^{\ast }(G)\le t^{+}(G)$ for every nontrivial connected graph $G$. We show that $t^{\ast }(G)\le \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^{\ast }(G)=b$ if and only if $a\le b\le \lfloor \frac{3n}{2}\rfloor$.