# Ordered-pair graphs

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:

1. there is an $n$ such that there are exactly $n^2$ vertices
2. there are exactly $n$ vertices $v$ with $v\rightarrow v$
3. each vertex has exactly $n$ incoming and $n$ outgoing arrows
4. the relation $x \sim_1 y$ which holds iff $(\exists z)\ x \rightarrow z \wedge\ y \rightarrow z$ is an equivalence relation
5. 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?

-
These are the 2-dimensional De Bruijn graphs. – Henning Makholm Oct 5 '11 at 21:36
Thanks, Henning! Great hint. – Hans Stricker Oct 5 '11 at 21:40