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).