Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
traceable number; upper traceable number; Hamiltonian number
traceable number; upper traceable number; Hamiltonian number
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.
References:
[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. DOI 10.1002/jgt.3190040310 | MR 0584677
[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. DOI 10.1016/0166-218X(83)90042-2 | MR 0683513
[3] J. C. Bermond: On Hamiltonian walks. Congr. Numer. 15 (1976), 41–51. MR 0398891 | Zbl 0329.05113
[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
[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
[6] G. Chartrand and P. Zhang: Introduction to Graph Theory. McGraw-Hill, Boston, 2005.
[7] S. E. Goodman and S. T. Hedetniemi: On Hamiltonian walks in graphs. Congr. Numer. (1973), 335–342. MR 0357223
[8] S. E. Goodman and S. T. Hedetniemi: On Hamiltonian walks in graphs. SIAM J. Comput. 3 (1974), 214–221. DOI 10.1137/0203017 | MR 0432492
[9] L. Nebeský: A generalization of Hamiltonian cycles for trees. Czech. Math. J. 26 (1976), 596–603. MR 0543670
[10] F. Okamoto, V. Saenpholphat and P. Zhang: Measures of traceability in graphs. Math. Bohem. 131 (2006), 63–83. MR 2211004
[11] V. Saenpholphat and P. Zhang: Graphs with prescribed order and Hamiltonian number. Congr. Numer. 175 (2005), 161–173. MR 2198624
[12] P. Vacek: On open Hamiltonian walks in graphs. Arch Math. (Brno) 27A (1991), 105–111. MR 1189647 | Zbl 0758.05067
Search
Partner of
