Measures of traceability in graphs
Varaporn Saenpholphat, Futaba Okamoto, Ping Zhang (2006)
Mathematica Bohemica
Similarity:
For a connected graph of order and an ordering , of the vertices of , , where is the distance between and . The traceable number of is defined by where the minimum is taken over all sequences of the elements of . It is shown that if is a nontrivial connected graph of order such that is the length of a longest path in and is the maximum size of a spanning linear forest in , then and both these bounds are sharp. We establish a formula for the traceable...