## On upper traceable numbers of graphs.(English)Zbl 1199.05095

Summary: For a connected graph $$G$$ of order $$n\geq 2$$ and a linear ordering $$s\: v_1,v_2,\dots ,v_n$$ of vertices of $$G$$, $$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 upper traceable number $$t^+(G)$$ of $$G$$ is $$t^+(G)= \max \{d(s)\}$$, where the maximum is taken over all linear orderings $$s$$ of vertices of $$G$$. It is known that if $$T$$ is a tree of order $$n\geq 3$$, then $$2n-3\leq t^+(T)\leq \lfloor {n^2/2}\rfloor -1$$ and $$t^+(T)\leq \lfloor {n^2/2} \rfloor -3$$ if $$T\neq P_n$$. All pairs $$n,k$$ for which there exists a tree $$T$$ of order $$n$$ and $$t^+(T)= k$$ are determined and a characterization of all those trees of order $$n\geq 4$$ with upper traceable number $$\lfloor {n^2/2}\rfloor -3$$ is established. For a connected graph $$G$$ of order $$n\geq 3$$, it is known that $$n-1\leq t^+(G)\leq \lfloor {n^2/2}\rfloor -1$$. We investigate the problem of determining possible pairs $$n,k$$ of positive integers that are realizable as the order and upper traceable number of some connected graph.

### MSC:

 05C12 Distance in graphs 05C45 Eulerian and Hamiltonian graphs

### Keywords:

traceable graph; traceable number; upper traceable number
Full Text: