Previous |  Up |  Next


Title: The upper traceable number of a graph (English)
Author: Okamoto, Futaba
Author: Zhang, Ping
Author: Saenpholphat, Varaporn
Language: English
Journal: Czechoslovak Mathematical Journal
ISSN: 0011-4642 (print)
ISSN: 1572-9141 (online)
Volume: 58
Issue: 1
Year: 2008
Pages: 271-287
Summary lang: English
Category: math
Summary: 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 \lbrace d(s)\rbrace $ and the upper traceable number $t^+(G)$ of $G$ is $t^+(G) = \max \lbrace d(s)\rbrace ,$ 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. (English)
Keyword: traceable number
Keyword: upper traceable number
Keyword: Hamiltonian number
MSC: 05C12
MSC: 05C45
idZBL: Zbl 1174.05040
idMR: MR2402537
Date available: 2009-09-24T11:54:48Z
Last updated: 2016-04-07
Stable URL:
Reference: [1] T. Asano, T. Nishizeki and T. Watanabe: An upper bound on the length of a Hamiltonian walk of a maximal planar graph.J. Graph Theory 4 (1980), 315–336. MR 0584677, 10.1002/jgt.3190040310
Reference: [2] T. Asano, T. Nishizeki and T. Watanabe: An approximation algorithm for the Hamiltonian walk problems on maximal planar graphs.Discrete Appl. Math. 5 (1983), 211–222. MR 0683513, 10.1016/0166-218X(83)90042-2
Reference: [3] J. C. Bermond: On Hamiltonian walks.Congr. Numer. 15 (1976), 41–51. Zbl 0329.05113, MR 0398891
Reference: [4] G. Chartrand, T. Thomas, V. Saenpholphat and P. Zhang: On the Hamiltonian number of a graph.Congr. Numer. 165 (2003), 51–64. MR 2049121
Reference: [5] G. Chartrand, T. Thomas, V. Saenpholphat and P. Zhang: A new look at Hamiltonian walks.Bull. Inst. Combin. Appl. 42 (2004), 37–52. MR 2082480
Reference: [6] G. Chartrand and P. Zhang: Introduction to Graph Theory.McGraw-Hill, Boston, 2005.
Reference: [7] S. E. Goodman and S. T. Hedetniemi: On Hamiltonian walks in graphs.Congr. Numer. (1973), 335–342. MR 0357223
Reference: [8] S. E. Goodman and S. T. Hedetniemi: On Hamiltonian walks in graphs.SIAM J. Comput. 3 (1974), 214–221. MR 0432492, 10.1137/0203017
Reference: [9] L. Nebeský: A generalization of Hamiltonian cycles for trees.Czech. Math. J. 26 (1976), 596–603. MR 0543670
Reference: [10] F. Okamoto, V. Saenpholphat and P. Zhang: Measures of traceability in graphs.Math. Bohem. 131 (2006), 63–83. MR 2211004
Reference: [11] V. Saenpholphat and P. Zhang: Graphs with prescribed order and Hamiltonian number.Congr. Numer. 175 (2005), 161–173. MR 2198624
Reference: [12] P. Vacek: On open Hamiltonian walks in graphs.Arch Math. (Brno) 27A (1991), 105–111. Zbl 0758.05067, MR 1189647


Files Size Format View
CzechMathJ_58-2008-1_16.pdf 278.8Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo