**
Czechoslovak Mathematical Journal, Vol. 58, No. 1, pp. 271-287, 2008
**

#
The upper traceable number of a graph

##
Futaba Okamoto, Ping Zhang, Varaporn Saenpholphat

* Futaba Okamoto*, Mathematics Department, University of Wisconsin-La Crosse, La Crosse, WI 54601, USA; * Varaporn Saenpholphat*, Department of Mathematics, Srinakharinwirot University, Sukhumvit Soi 23, Bangkok, 10110, Thailand; * Ping Zhang*, Department of Mathematics Western Michigan University Kalamazoo, MI 49008, USA

**Abstract:** For a nontrivial connected graph $G$ of order $n$ and a linear ordering $s v_1, v_2, \ldots, v_n$ of vertices of $G$, define $d(s) = \sum_{i=1}^{n-1} d(v_i, v_{i+1})$. The traceable number $t(G)$ of a graph $G$ is $t(G) = \min\{d(s)\}$ and the upper traceable number $t^+(G)$ of $G$ is $t^+(G) = \max\{d(s)\},$ where the minimum and maximum are taken over all linear orderings $s$ of vertices of $G$. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs $G$ for which $t^+(G)- t(G) = 1$ are characterized and a formula for the upper traceable number of a tree is established.

**Keywords:** traceable number, upper traceable number, Hamiltonian 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.

Subscribers of Springer need to access the articles on their site, which is http://www.springeronline.com/10587.