On Traceable and Upper Traceable Numbers of Graphs

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})$. 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)$. Consequently, $t(G)\le t^{+}(G)$. It is known that $n-1\le t(G)\le 2n-4$ and $n-1\le t^{+}(G)\le \lfloor \frac{n^2}{2}\rfloor –1$ for every connected graph $G$ of order $n\ge 3$ and, furthermore, for every pair $n,A$ of integers with $2n-1\le A\le 2n-4$ there exists a graph of order $n$ whose traceable number equals $A$. In this work, we determine all pairs $A,B$ of positive integers with $A\le B$ that are realizable as the traceable number and upper traceable number, respectively, of some graph. It is also determined for which pairs $n,B$ of integers with $n-1\le B\le \lfloor \frac{n^2}{2}\rfloor –1$ there exists a graph whose order equals $n$ and upper traceable number equals $\mu$.