Consider a (finite) set $S$ and the digraph $G$ with vertex set $V(G) = S^2$, i.e. the ordered pairs over $S$. Let there be an arrow from $(v,w)$ to $(x,y)$ iff $v = y$.
How can these "ordered pair graphs" be abstractly characterized (up to isomorphism)?
Some necessary conditions for a graph to be an ordered pair graph are obvious:
- there is an $n$ such that there are exactly $n^2$ vertices
- there are exactly $n$ vertices $v$ with $v\rightarrow v$
- each vertex has exactly $n$ incoming and $n$ outgoing arrows
- the relation $x \sim_1 y$ which holds iff $(\exists z)\ x \rightarrow z \wedge\ y \rightarrow z$ is an equivalence relation
- the relation $x \sim_2 y$ which holds iff $(\exists z)\ z \rightarrow x \wedge\ z \rightarrow y$ is an equivalence relation
Can it be shown that some of the conditions above depend on others, esp. on (4) and/or (5)?
Can this set of conditions be completed to characterize ordered pair graphs up to isomorphism?