Pair diagram
The cartesian product of graphs has many applications. As the upper bound of two
graphs, it compares paths between two different diagrams (or two paths in the same
diagram). It also appears in second moment (and therefore variance) calculation of path
frequencies. As an example, Figure 14 shows the pair
diagram (cartesian product of a graph with itself) for the 
de Bruijn diagram of Figure 7.
Figure 14: Sixteen node pair diagram for a 
de Bruijn diagram, an image of which is visible along the diagonal as
well as in horizontal and vertical section.
Its connectivity matrix is
0.30em
whose tensor product form is clearly visible.
It is not always necessary to distinguish between the members of a pair; the arrows in a graph require links to be defined as ordered pairs of nodes, but that does not necessarily require that a pair of links be taken in any particular order, for example.
Figure 15 shows the unordered pair graph of the
two-stage de Bruijn diagram for 
automata, whose
connectivity matrix is the symmetrized Kronecker product of the individual connectivity
matrices. It has fewer nodes, yet the full Kronecker product is homomorphic to it, giving
it computational and visual advantages.
Both versions satisfy Richard's criterion [6] for duality, presumably participating in the same kind of dual chains as the de Bruijn diagrams themselves.
Figure 15: Ten node unordered pair diagram for a 
de Bruijn diagram, an image of which (the diagonal) is visible around
the circumference.
The connectivity matrix for unordered pairs is
0.50em
while the homomorphism matrix between the two versions is
0.50em
Multiplicities spoil comparing PX to Xp:
0.24em
But the discussion surrounding Equations 3 and 16, gives a choice: 1) reduce PX to a boolean matrix whose nonzero entries are ones, or 2) weight the links in p with the number of links per pair to get a numerically valid comparison.
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx