Dyck Graph

The Dyck graph is the unique cubic symmetric graph on 32 nodes, illustrated above in a number of drawings. It is denoted in the Foster census of cubic symmetric graphs and Ct71 in the tabulation of vertex-transitive graphs by Read and Wilson (1998).

The Dyck graph can be represented in LCF notation as , , and , illustrated above.

It is also a unit-distance graph, as illustrated above in six unit-distance embeddings (Gerbracht 2008, pers. comm., Jan. 4, 2010).

There is a beautiful construction of the Dyck graph due to Eppstein (2007) which takes the 32 permutations of the vectors (0, 0, 0), (0, 0, 1), (0, 1, 3), (0, 2, 3), (0, 2, 2), (1, 1, 3), (1, 1, 2), (1, 2, 2), (2, 3, 3), and (3, 3, 3) as the vertices and joins pairs of vertices whose difference contains precisely two zeros. This gives a three-dimensional xyz embedding of the Dyck graph as illustrated above.

The Dyck graph has graph crossing number and rectilinear crossing number at most 12, as illustrated above.

On the other hand, the Dyck graph is toroidal, as illustrated above, meaning it has toroidal crossing number 0. The left-hand drawing shows an embedding in a fundamental region whose paired boundary sides are identified to form a torus. The right-hand drawing shows a finite patch of the corresponding periodic lift, illustrating how edges continue across these boundaries and where corresponding vertices in different regions represent the same vertex on the torus.

The plots above show the adjacency matrix, incidence matrix, and graph distance matrix for the Dyck graph.

The Dyck graph has graph spectrum

It is implemented in the Wolfram Language as GraphData["DyckGraph"].