| Title:
|
On upper traceable numbers of graphs (English) |
| Author:
|
Okamoto, Futaba |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
133 |
| Issue:
|
4 |
| Year:
|
2008 |
| Pages:
|
389-405 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
traceable graph |
| Keyword:
|
traceable number |
| Keyword:
|
upper traceable number |
| MSC:
|
05C12 |
| MSC:
|
05C45 |
| idZBL:
|
Zbl 1199.05095 |
| idMR:
|
MR2472487 |
| DOI:
|
10.21136/MB.2008.140628 |
| . |
| Date available:
|
2010-07-20T17:39:10Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140628 |
| . |
| Reference:
|
[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. Zbl 0433.05037, MR 0584677, 10.1002/jgt.3190040310 |
| Reference:
|
[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. MR 0683513, 10.1016/0166-218X(83)90042-2 |
| Reference:
|
[3] Bermond, J. C.: On Hamiltonian walks.Congr. Numer. 15 (1976), 41-51. Zbl 0329.05113, MR 0398891 |
| Reference:
|
[4] Chartrand, G., Kronk, H. V.: On a special class of hamiltonian graphs.Comment. Math. Helv. 44 (1969), 84-88. Zbl 0169.55501, MR 0239995, 10.1007/BF02564514 |
| Reference:
|
[5] Chartrand, G., Saenpholphat, V., Thomas, T., Zhang, P.: A new look at Hamiltonian walks.Bull. Inst. Combin. Appl. 42 (2004), 37-52. MR 2082480 |
| Reference:
|
[6] Chartrand, G., Zhang, P.: Introduction to Graph Theory.McGraw-Hill, Boston (2005). Zbl 1096.05001 |
| Reference:
|
[7] Goodman, S. E., Hedetniemi, S. T.: On Hamiltonian walks in graphs.SIAM J. Comput. 3 (1974), 214-221. Zbl 0269.05113, MR 0432492, 10.1137/0203017 |
| Reference:
|
[8] Okamoto, F., Saenpholphat, V., Zhang, P.: Measures of traceability in graphs.Math. Bohem. 131 (2006), 63-83. Zbl 1112.05032, MR 2211004 |
| Reference:
|
[9] Okamoto, F., Saenpholphat, V., Zhang, P.: The upper traceable number of a graph.(to appear) in Czech. Math. J. Zbl 1174.05040, MR 2402537 |
| Reference:
|
[10] Nebeský, L.: A generalization of Hamiltonian cycles for trees.Czech. Math. J. 26 (1976), 596-603. MR 0543670 |
| Reference:
|
[11] Thomassen, C.: On randomly Hamiltonian graphs.Math. Ann. 200 (1973), 195-208. Zbl 0233.05121, MR 0325456, 10.1007/BF01425231 |
| Reference:
|
[12] Vacek, P.: On open Hamiltonian walks in graphs.Arch. Math., Brno 27A (1991), 105-111. Zbl 0758.05067, MR 1189647 |
| Reference:
|
[13] Vacek, P.: Bounds of lengths of open Hamiltonian walks.Arch. Math., Brno 28 (1992), 11-16. Zbl 0782.05056, MR 1201861 |
| . |
