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.


[Previous Article] [Contents of This Number] [Contents of Czechoslovak Mathematical Journal]