Geodesic
On upper traceable numbers of graphs
Mathematica Bohemica, Tome 133 (2008) no. 4, pp. 389-405

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

MR Zbl
For a connected graph $G$ of order $n\ge 2$ and a linear ordering $s\colon v_1,v_2,\ldots ,v_n$ of vertices of $G$, $d(s)= \sum _{i=1}^{n-1}d(v_i,v_{i+1})$, where $d(v_i,v_{i+1})$ is the distance between $v_i$ and $v_{i+1}$. The upper traceable number $t^+(G)$ of $G$ is $t^+(G)= \max \{d(s)\}$, where the maximum is taken over all linear orderings $s$ of vertices of $G$. It is known that if $T$ is a tree of order $n\ge 3$, then $2n-3\le t^+(T)\le \lfloor {n^2/2}\rfloor -1$ and $t^+(T)\le \lfloor {n^2/2}\rfloor -3$ if $T\ne P_n$. All pairs $n,k$ for which there exists a tree $T$ of order $n$ and $t^+(T)= k$ are determined and a characterization of all those trees of order $n\ge 4$ with upper traceable number $\lfloor {n^2/2}\rfloor -3$ is established. For a connected graph $G$ of order $n\ge 3$, it is known that $n-1\le t^+(G)\le \lfloor {n^2/2}\rfloor -1$. We investigate the problem of determining possible pairs $n,k$ of positive integers that are realizable as the order and upper traceable number of some connected graph.
For a connected graph $G$ of order $n\ge 2$ and a linear ordering $s\colon v_1,v_2,\ldots ,v_n$ of vertices of $G$, $d(s)= \sum _{i=1}^{n-1}d(v_i,v_{i+1})$, where $d(v_i,v_{i+1})$ is the distance between $v_i$ and $v_{i+1}$. The upper traceable number $t^+(G)$ of $G$ is $t^+(G)= \max \{d(s)\}$, where the maximum is taken over all linear orderings $s$ of vertices of $G$. It is known that if $T$ is a tree of order $n\ge 3$, then $2n-3\le t^+(T)\le \lfloor {n^2/2}\rfloor -1$ and $t^+(T)\le \lfloor {n^2/2}\rfloor -3$ if $T\ne P_n$. All pairs $n,k$ for which there exists a tree $T$ of order $n$ and $t^+(T)= k$ are determined and a characterization of all those trees of order $n\ge 4$ with upper traceable number $\lfloor {n^2/2}\rfloor -3$ is established. For a connected graph $G$ of order $n\ge 3$, it is known that $n-1\le t^+(G)\le \lfloor {n^2/2}\rfloor -1$. We investigate the problem of determining possible pairs $n,k$ of positive integers that are realizable as the order and upper traceable number of some connected graph.
DOI : 10.21136/MB.2008.140628
Classification : 05C12, 05C45
Keywords: traceable graph; traceable number; upper traceable number 
Okamoto, Futaba; Zhang, Ping. On upper traceable numbers of graphs. Mathematica Bohemica, Tome 133 (2008) no. 4, pp. 389-405. doi: 10.21136/MB.2008.140628
@article{10_21136_MB_2008_140628,
     author = {Okamoto, Futaba and Zhang, Ping},
     title = {On upper traceable numbers of graphs},
     journal = {Mathematica Bohemica},
     pages = {389--405},
     year = {2008},
     volume = {133},
     number = {4},
     doi = {10.21136/MB.2008.140628},
     mrnumber = {2472487},
     zbl = {1199.05095},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2008.140628/}
}
TY  - JOUR
AU  - Okamoto, Futaba
AU  - Zhang, Ping
TI  - On upper traceable numbers of graphs
JO  - Mathematica Bohemica
PY  - 2008
SP  - 389
EP  - 405
VL  - 133
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2008.140628/
DO  - 10.21136/MB.2008.140628
LA  - en
ID  - 10_21136_MB_2008_140628
ER  - 
%0 Journal Article
%A Okamoto, Futaba
%A Zhang, Ping
%T On upper traceable numbers of graphs
%J Mathematica Bohemica
%D 2008
%P 389-405
%V 133
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2008.140628/
%R 10.21136/MB.2008.140628
%G en
%F 10_21136_MB_2008_140628

[1] Asano, T., Nishizeki, T., Watanabe, T.: An upper bound on the length of a Hamiltonian walk of a maximal planar graph. J. Graph Theory 4 (1980), 315-336. | DOI | MR | Zbl

[2] Asano, T., Nishizeki, T., Watanabe, T.: An approximation algorithm for the Hamiltonian walk problems on maximal planar graphs. Discrete Appl. Math. 5 (1983), 211-222. | DOI | MR

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

[4] Chartrand, G., Kronk, H. V.: On a special class of hamiltonian graphs. Comment. Math. Helv. 44 (1969), 84-88. | DOI | MR | Zbl

[5] Chartrand, G., Saenpholphat, V., Thomas, T., Zhang, P.: A new look at Hamiltonian walks. Bull. Inst. Combin. Appl. 42 (2004), 37-52. | MR

[6] Chartrand, G., Zhang, P.: Introduction to Graph Theory. McGraw-Hill, Boston (2005). | Zbl

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

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

[9] Okamoto, F., Saenpholphat, V., Zhang, P.: The upper traceable number of a graph. (to appear) in Czech. Math. J. | MR | Zbl

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

[11] Thomassen, C.: On randomly Hamiltonian graphs. Math. Ann. 200 (1973), 195-208. | DOI | MR | Zbl

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

[13] Vacek, P.: Bounds of lengths of open Hamiltonian walks. Arch. Math., Brno 28 (1992), 11-16. | MR | Zbl

Cité par Sources :