Isomorphisms of directed ${\overrightarrow{P}}_3$-graphs

Abstract

The directed ${\overrightarrow{P}}_k$-graph of a digraph $D$ is obtained by representing the directed paths on $k$ vertices of $D$ by vertices. Two such vertices are joined by an arc whenever the corresponding directed paths in $D$ form a directed path on $k+1$ vertices or a directed cycle on $k$ vertices in $D$. In this paper, we give a necessary and sufficient condition for two digraphs with isomorphic ${\overrightarrow{P}}_3$-graphs. This improves a previous result, where some additional conditions were imposed.