Geodesic
The upper traceable number of a graph
Czechoslovak Mathematical Journal, Tome 58 (2008) no. 1, pp. 271-287

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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},
     publisher = {mathdoc},
     volume = {58},
     number = {1},
     year = {2008},
     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
PB  - mathdoc
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
%I mathdoc
%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/