Ed Pegg recently asked me whether various cubic Hamiltonian graphs were xyz graphs, and to test this out I added some code for LCF Notation to GraphExamples.py in PADS along with several specific graphs that can be described using this notation.

It turns out that most of the named graphs I tried are not xyz, but two of them are: the Pappus graph and the Dyck graph. The Pappus graph was already shown as the rightmost graph in the figure from this post. The Dyck graph, it turns out, was described indirectly at the bottom of the same post: for any \( n \), one can embed an xyz graph with \( 2n^2 \) points within an \( n\times n\times n \) grid, at the points \( (x,y,z) \) satisfying \( x+y+z\in\{0,1\}\pmod{n} \). For each \( n \), this produces a cubic symmetric graph: \( n=2 \) gives the cube (the unique 8-vertex cubic symmetric graph), \( n=3 \) gives the Pappus graph (the unique 18-vertex cubic symmetric graph), \( n=4 \) gives the Dyck graph (the unique 32-vertex cubic symmetric graph), etc.

Here's a picture of the xyz embedding of the Dyck graph:

xyz representation of the Dyck graph

There is only one way of partitioning the edges of the Dyck graph into three subsets that form the parallel edge classes of an xyz representation.





Comments:

mcfnord:
2007-10-17T03:09:23Z
trippy
11011110:
2007-10-17T06:49:54Z
*uses psychadelic icon*