Recognizing k-path graphs

Recognizing k-path graphs

0.00 Avg rating0 Votes
Article ID: iaor20012904
Country: Netherlands
Volume: 99
Issue: 1/3
Start Page Number: 169
End Page Number: 181
Publication Date: Feb 2000
Journal: Discrete Applied Mathematics
Authors:
Keywords: networks: path
Abstract:

The k-path graph Pk(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≥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≥1 and some graph H of minimum degree at least k+1 with G=Pk(H). In this case, we show that k and H are unique, extending previous uniqueness results by Xueliang Li.

Reviews

Required fields are marked *. Your email address will not be published.