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 (MSC 2000): 05C12, 05C45

Full text available as PDF (smallest), as compressed PostScript (.ps.gz) or as raw PostScript (.ps).

Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris@myris.cz.