**
MATHEMATICA BOHEMICA, Vol. 131, No. 1, pp. 63-84 (2006)
**

#
Measures of traceability in graphs

##
Varaporn Saenpholphat, Futaba Okamoto, Ping Zhang

* Varaporn Saenpholphat*, Department of Mathematics, Srinakharinwirot University, Sukhumvit Soi 23, Bangkok, 10110, Thailand; * Futaba Okamoto*, * Ping Zhang*, Department of Mathematics, Western Michigan University, Kalamazoo, MI 49008, USA, e-mail: ` ping.zhang@wmich.edu`

**Abstract:** For a connected graph $G$ of order $n \geq3$ 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\{d(s)\right\},$ 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) \le2n-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 \ge3$, then $t(G)\le2n-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\{d(s)\}$, 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 $\hcon(G)$ of a connected graph $G$ is defined by $\hcon(G) = \sum_{v \in V(G)} t(v).$ We establish sharp bounds for $\hcon(G)$ of a connected graph $G$ in terms of its order.

**Keywords:** traceable graph, Hamiltonian graph, Hamiltonian-connected graph

**Classification (MSC2000):** 05C12, 05C45

**Full text of the article:**

[Previous Article] [Next Article] [Contents of this Number] [Journals Homepage]

*
© 2006–2010
FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition
*