P-3-ISOMORPHISMS FOR GRAPHS

The P-3-graph of a finite simple graph G is the graph whose vertices a re the 3-vertex paths of G, with adjacency between two such paths when ever their union is a 4-vertex path or a 3-cycle. In this paper we sho w that connected finite simple graphs G and H with isomorphic P-3-grap hs are either isomorphic or part of three exceptional families. We als o characterize all isomorphisms between P-3-graphs in terms of the ori ginal graphs. (C) 1997 John Wiley & Sons, Inc.