  Hung and Chang showed that for all k>=1 an interval graph has a path cover of
size at most k if and only if its scattering number is at most k. They also
showed that an interval graph has a Hamilton cycle if and only if its
scattering number is at most 0. We complete this characterization by proving
that for all k<=-1 an interval graph is -(k+1)-Hamilton-connected if and only
if its scattering number is at most k. We also give an O(m+n) time algorithm
for computing the scattering number of an interval graph with n vertices an m
edges, which improves the O(n^4) time bound of Kratsch, Kloks and M\"uller. As
a consequence of our two results the maximum k for which an interval graph is
k-Hamilton-connected can be computed in O(m+n) time.

Data Structures and Algorithms