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

Okamoto, Futaba; Zhang, Ping

Math. Bohem. 133, No. 4, 389-405 (2008).

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