"Isometry" and "product" certainly need
a word of explanation. Isometry requires preservation of the shortest
path distance, that is, any two vertices of \(G\)  are sent to two
vertices at the same distance in the product. The product in question
is the strong product, which is the canonical product in the
category of undirected graphs with loops; namely, two vertices in
such a product are adjacent if and only if all pairs of their
corresponding coordinates form edges (which may be loops). Now, for
directed graphs (binary relations with loops) the embedding question is more intricate. The strong product one
considers here is, of course, the direct product for reflexive
relations, but the potential factors are not just those directed graphs whose
symmetric closures constitute undirected paths (see Kabil and Pouzet [1]}). Distance and thus
isometry have a natural meaning here, too – but one needs to measure
distances by sets of words over a two or three lettter alphabet
rather than numbers. The approriate notion of distance for directed
graphs was introduced by Quilliot [2]} and is subsumed in the general
approach taken by Jawhari, Misane and Pouzet [3]} and further developped by Pouzet and Rosenberg [4]}. Let us focus on
the case of oriented graphs (with loops), i.e., reflexive
antisymmetric binary relations as in this case a two letter alphabet (distinguishing 'forward' and 'backward') will do: an oriented graph is a
directed graph in which every pair of vertices is linked by at most
one arc. The oriented analogues of undirected complete graphs, for
instance, are the tournaments. The oriented versions of undirected
paths are called zigzags, see Figure 1.
