P3-isomorphisms for graphs

The P₃-graph of a finite simple graph G is the graph whose vertices are the 3-vertex paths of G, with adjacency between two such paths whenever their union is a 4-vertex path or a 3-cycle. In this paper we show that connected fnite simple graphs G and H with isomorphic P₃-graphs are either isomorphic or part of three exceptional families. We also characterize all isomorphisms between P₃-graphs in terms of the original graphs. © 1997 John Wiley & Sons, Inc. J Graph Theory 26:35–51, 1997