Recognizing k-path graphs

The k-path graph P-k(H) Of a graph H has all length-k paths of H as vertices; two such vertices are adjacent in the new graph if their union forms a path or cycle of length k + 1 in H, and if the common edges of both paths form a path of length k - 1. In this paper we give a (nonpolynomial) recognition algorithm for k-path graphs, for every integer k greater than or equal to 2. The algorithm runs in polynomial time if we are only interested in k-path graphs of graphs of high enough minimum degree. We also present an O(\V\(4))-time algorithm that decides whether for any input graph G = (V,E) there exist some integer k greater than or equal to 1 and some graph H of minimum degree at least k + 1 with G = P-k(H). If it is, we show that Ic and H are unique, extending previous uniqueness results by Xueliang Li. (C) 2000 Elsevier Science B.V. All rights reserved.