| 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:
|
2020-07-03 |
| 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 |
| . |
