On Traceable and Upper Traceable Numbers of Graphs

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})\). 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) \leq t^+(G)\). It is known that \(n-1 \leq t(G) \leq 2n-4\) and \(n-1 \leq t^+(G) \leq \left\lfloor \frac{n^2}{2} \right\rfloor – 1\) for every connected graph \(G\) of order \(n \geq 3\) and, furthermore, for every pair \(n, A\) of integers with \(2n-1 \leq A \leq 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 \leq 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 \leq B \leq \left\lfloor \frac{n^2}{2} \right\rfloor – 1\) there exists a graph whose order equals \(n\) and upper traceable number equals \(\mu\).