Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
traceable graph; Hamiltonian graph; Hamiltonian-connected graph
traceable graph; Hamiltonian graph; Hamiltonian-connected graph
Summary:
For a connected graph $G$ of order $n \ge 3$ and an ordering $s\: v_1$, $v_2, \cdots , v_n$ of the 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 traceable number $t(G)$ of $G$ is defined by $t(G) = \min \left\rbrace d(s)\right\lbrace ,$ where the minimum is taken over all sequences $s$ of the elements of $V(G)$. It is shown that if $G$ is a nontrivial connected graph of order $n$ such that $l$ is the length of a longest path in $G$ and $p$ is the maximum size of a spanning linear forest in $G$, then $2n-2 - p \le t(G) \le 2n-2 - l$ and both these bounds are sharp. We establish a formula for the traceable number of every tree in terms of its order and diameter. It is shown that if $G$ is a connected graph of order $n \ge 3$, then $t(G)\le 2n-4$. We present characterizations of connected graphs of order $n$ having traceable number $2n-4$ or $2n-5$. The relationship between the traceable number and the Hamiltonian number (the minimum length of a closed spanning walk) of a connected graph is studied. The traceable number $t(v)$ of a vertex $v$ in a connected graph $G$ is defined by $t(v) = \min \lbrace d(s)\rbrace $, where the minimum is taken over all linear orderings $s$ of the vertices of $G$ whose first term is $v$. We establish a formula for the traceable number $t(v)$ of a vertex $v$ in a tree. The Hamiltonian-connected number $\mathop {\mathrm hcon}(G)$ of a connected graph $G$ is defined by $\mathop {\mathrm hcon}(G) = \sum _{v \in V(G)} t(v).$ We establish sharp bounds for $\mathop {\mathrm hcon}(G)$ of a connected graph $G$ in terms of its order.
References:
[1] T. Asano, T. Nishizeki, 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 10.1002/jgt.3190040310 | MR 0584677
[2] T. Asano, T. Nishizeki, T. Watanabe: An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs. Discrete Appl. Math. 5 (1983), 211–222. DOI 10.1016/0166-218X(83)90042-2 | MR 0683513
[3] J. C. Bermond: On Hamiltonian walks. Congr. Numerantium 15 (1976), 41–51. MR 0398891 | Zbl 0329.05113
[4] G. Chartrand, T. Thomas, V. Saenpholphat, P. Zhang: On the Hamiltonian number of a graph. Congr. Numerantium 165 (2003), 51–64. MR 2049121
[5] G. Chartrand, T. Thomas, V. Saenpholphat, P. Zhang: A new look at Hamiltonian walks. Bull. Inst. Combin. Appl. 42 (2004), 37–52. MR 2082480
[6] G. Chartrand, P. Zhang: Introduction to Graph Theory. McGraw-Hill, Boston, 2005.
[7] S. E. Goodman, S. T. Hedetniemi: On Hamiltonian walks in graphs. Congr. Numerantium (1973), 335–342. MR 0357223
[8] S. E. Goodman, S. T. Hedetniemi: On Hamiltonian walks in graphs. SIAM J. Comput. 3 (1974), 214–221. DOI 10.1137/0203017 | MR 0432492
[9] L. Nebeský: A generalization of Hamiltonian cycles for trees. Czech. Math. J. 26 (1976), 596–603. MR 0543670
[10] L. Lesniak: Eccentric sequences in graphs. Period. Math. Hungar 6 (1975), 287–293. DOI 10.1007/BF02017925 | MR 0406872 | Zbl 0363.05053
[11] P. Vacek: On open Hamiltonian walks in graphs. Arch. Math., Brno 27A (1991), 105–111. MR 1189647 | Zbl 0758.05067
Search
Partner of
