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 (MSC 2000): 05C12, 05C45
Full text available as PDF (smallest), as compressed PostScript (.ps.gz) or as raw PostScript (.ps).
Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris@myris.cz.
