POWERS OF HAMILTONIAN PATHS IN INTERVAL-GRAPHS

We give a simple proof that the obvious necessary conditions for a gra ph to contain the k(th) power of a Hamiltonian path are sufficient for the class of interval graphs. The proof is based on showing that a gr eedy algorithm tests for the existence of Hamiltonian path powers in i nterval graphs. We will also discuss covers by powers of paths and ana logues of the Hamiltonian completion number. (C) 1998 John Wiley & Son s, Inc.