Previous |  Up |  Next

# Article

 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: http://hdl.handle.net/10338.dmlcz/128257 . 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

Files Size Format View
CzechMathJ_58-2008-1_16.pdf 278.8Kb application/pdf View/Open

Partner of