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.


05C12 Distance in graphs
05C45 Eulerian and Hamiltonian graphs
Full Text: EuDML EMIS