Geodesic
The upper traceable number of a graph
Czechoslovak Mathematical Journal, Tome 58 (2008) no. 1, pp. 271-287 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C12, 05C45
Keywords: traceable number; upper traceable number; Hamiltonian number 
@article{CMJ_2008_58_1_a15,
     author = {Okamoto, Futaba and Zhang, Ping and Saenpholphat, Varaporn},
     title = {The upper traceable number of a graph},
     journal = {Czechoslovak Mathematical Journal},
     pages = {271--287},
     year = {2008},
     volume = {58},
     number = {1},
     mrnumber = {2402537},
     zbl = {1174.05040},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2008_58_1_a15/}
}
TY  - JOUR
AU  - Okamoto, Futaba
AU  - Zhang, Ping
AU  - Saenpholphat, Varaporn
TI  - The upper traceable number of a graph
JO  - Czechoslovak Mathematical Journal
PY  - 2008
SP  - 271
EP  - 287
VL  - 58
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/CMJ_2008_58_1_a15/
LA  - en
ID  - CMJ_2008_58_1_a15
ER  - 
%0 Journal Article
%A Okamoto, Futaba
%A Zhang, Ping
%A Saenpholphat, Varaporn
%T The upper traceable number of a graph
%J Czechoslovak Mathematical Journal
%D 2008
%P 271-287
%V 58
%N 1
%U http://geodesic.mathdoc.fr/item/CMJ_2008_58_1_a15/
%G en
%F CMJ_2008_58_1_a15
Okamoto, Futaba; Zhang, Ping; Saenpholphat, Varaporn. The upper traceable number of a graph. Czechoslovak Mathematical Journal, Tome 58 (2008) no. 1, pp. 271-287. http://geodesic.mathdoc.fr/item/CMJ_2008_58_1_a15/

[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 | MR

[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 | MR

[3] J. C. Bermond: On Hamiltonian walks. Congr. Numer. 15 (1976), 41–51. | MR | Zbl

[4] G. Chartrand, T. Thomas, V. Saenpholphat and P. Zhang: On the Hamiltonian number of a graph. Congr. Numer. 165 (2003), 51–64. | MR

[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

[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

[8] S. E. Goodman and S. T. Hedetniemi: On Hamiltonian walks in graphs. SIAM J. Comput. 3 (1974), 214–221. | DOI | MR

[9] L. Nebeský: A generalization of Hamiltonian cycles for trees. Czech. Math. J. 26 (1976), 596–603. | MR

[10] F. Okamoto, V. Saenpholphat and P. Zhang: Measures of traceability in graphs. Math. Bohem. 131 (2006), 63–83. | MR

[11] V. Saenpholphat and P. Zhang: Graphs with prescribed order and Hamiltonian number. Congr. Numer. 175 (2005), 161–173. | MR

[12] P. Vacek: On open Hamiltonian walks in graphs. Arch Math. (Brno) 27A (1991), 105–111. | MR | Zbl