Futaba Okamoto, Mathematics Department, University of Wisconsin - La Crosse, La Crosse, WI 54601, USA, Ping Zhang, Department of Mathematics, Western Michigan University, Kalamazoo, MI 49008, USA, e-mail: ping.zhang@wmich.edu
Abstract: For a connected graph $G$ of order $n\ge2$ and a linear ordering $s v_1,v_2,\ldots,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\ge3$, then $2n-3\le t^+(T)\le\lfloor{n^2/2}\rfloor-1$ and $t^+(T)\le\lfloor{n^2/2}\rfloor-3$ if $T\ne 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\ge4$ with upper traceable number $\lfloor{n^2/2}\rfloor-3$ is established. For a connected graph $G$ of order $n\ge3$, it is known that $n-1\le t^+(G)\le\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.
Keywords: traceable graph, traceable number, upper traceable number
Classification (MSC2000): 05C12, 05C45
Full text of the article: