zbMATH — the first resource for mathematics

Measures of traceability in graphs. (English) Zbl 1112.05032
Summary: For a connected graph $$G$$ of order $$n \geq 3$$ and an ordering $$s\: v_1$$, $$v_2, \dots , 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 \leq t(G) \leq 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 \geq 3$$, then $$t(G)\leq 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 \{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 $$\text{hcon} (G)$$ of a connected graph $$G$$ is defined by $$\text{hcon} (G) = \sum _{v \in V(G)} t(v).$$ We establish sharp bounds for $$\text{hcon} (G)$$ of a connected graph $$G$$ in terms of its order.

MSC:
 05C12 Distance in graphs 05C45 Eulerian and Hamiltonian graphs
Full Text: