Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.