×

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
PDFBibTeX XMLCite
Full Text: EuDML Link