Geodesic
Measures of traceability in graphs
Mathematica Bohemica, Tome 131 (2006) no. 1, pp. 63-84

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 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.
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.
DOI : 10.21136/MB.2006.134076
Classification : 05C12, 05C45
Keywords: traceable graph; Hamiltonian graph; Hamiltonian-connected graph 
Saenpholphat, Varaporn; Okamoto, Futaba; Zhang, Ping. Measures of traceability in graphs. Mathematica Bohemica, Tome 131 (2006) no. 1, pp. 63-84. doi: 10.21136/MB.2006.134076
@article{10_21136_MB_2006_134076,
     author = {Saenpholphat, Varaporn and Okamoto, Futaba and Zhang, Ping},
     title = {Measures of traceability in graphs},
     journal = {Mathematica Bohemica},
     pages = {63--84},
     year = {2006},
     volume = {131},
     number = {1},
     doi = {10.21136/MB.2006.134076},
     mrnumber = {2211004},
     zbl = {1112.05032},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2006.134076/}
}
TY  - JOUR
AU  - Saenpholphat, Varaporn
AU  - Okamoto, Futaba
AU  - Zhang, Ping
TI  - Measures of traceability in graphs
JO  - Mathematica Bohemica
PY  - 2006
SP  - 63
EP  - 84
VL  - 131
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2006.134076/
DO  - 10.21136/MB.2006.134076
LA  - en
ID  - 10_21136_MB_2006_134076
ER  - 
%0 Journal Article
%A Saenpholphat, Varaporn
%A Okamoto, Futaba
%A Zhang, Ping
%T Measures of traceability in graphs
%J Mathematica Bohemica
%D 2006
%P 63-84
%V 131
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2006.134076/
%R 10.21136/MB.2006.134076
%G en
%F 10_21136_MB_2006_134076

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

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

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

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

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

[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

[8] S. E. Goodman, 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] L. Lesniak: Eccentric sequences in graphs. Period. Math. Hungar 6 (1975), 287–293. | DOI | MR | Zbl

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

Cité par Sources :