×

The upper traceable number of a graph. (English) Zbl 1174.05040

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 \{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.

MSC:

05C12 Distance in graphs
05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI EuDML Link

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. · Zbl 0433.05037 · doi:10.1002/jgt.3190040310
[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. · Zbl 0511.05042 · doi:10.1016/0166-218X(83)90042-2
[3] J. C. Bermond: On Hamiltonian walks. Congr. Numer. 15 (1976), 41–51.
[4] G. Chartrand, T. Thomas, V. Saenpholphat and P. Zhang: On the Hamiltonian number of a graph. Congr. Numer. 165 (2003), 51–64. · Zbl 1043.05041
[5] G. Chartrand, T. Thomas, V. Saenpholphat and P. Zhang: A new look at Hamiltonian walks. Bull. Inst. Combin. Appl. 42 (2004), 37–52. · Zbl 1056.05093
[6] G. Chartrand and P. Zhang: Introduction to Graph Theory. McGraw-Hill, Boston, 2005. · Zbl 1096.05001
[7] S. E. Goodman and S. T. Hedetniemi: On Hamiltonian walks in graphs. Congr. Numer. (1973), 335–342. · Zbl 0321.05133
[8] S. E. Goodman and S. T. Hedetniemi: On Hamiltonian walks in graphs. SIAM J. Comput. 3 (1974), 214–221. · Zbl 0288.05121 · doi:10.1137/0203017
[9] L. Nebeský: A generalization of Hamiltonian cycles for trees. Czech. Math. J. 26 (1976), 596–603. · Zbl 0365.05030
[10] F. Okamoto, V. Saenpholphat and P. Zhang: Measures of traceability in graphs. Math. Bohem. 131 (2006), 63–83. · Zbl 1112.05032
[11] V. Saenpholphat and P. Zhang: Graphs with prescribed order and Hamiltonian number. Congr. Numer. 175 (2005), 161–173. · Zbl 1092.05021
[12] P. Vacek: On open Hamiltonian walks in graphs. Arch Math. (Brno) 27A (1991), 105–111. · Zbl 0758.05067
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.