Dyck Graph

The Dyck graph is unique cubic symmetric graph on 32 nodes, illustrated above in a number of embeddings. 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).

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

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

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

There is a beautiful construction of the Dyck graph due to D. Eppstein 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 plots above show the adjacency, incidence, and graph distance matrices for the Dyck graph.

The Dyck graph has graph spectrum

The following table summarizes some properties of the Dyck graph.

property	value
automorphism group order	192
characteristic polynomial
chromatic number	2
chromatic polynomial	?
claw-free	no
clique number	2
graph complement name	?
determined by spectrum	no
diameter	5
distance-regular graph	no
dual graph name	Shrikhande graph
edge chromatic number	3
edge connectivity	3
edge count	48
edge transitive	yes
Eulerian	no
girth	6
Hamiltonian	yes
Hamiltonian cycle count	120
Hamiltonian path count	?
integral graph	no
independence number	16
line graph	no
perfect matching graph	no
planar	no
polyhedral graph	no
radius	5
regular	yes
square-free	yes
symmetric	yes
traceable	yes
triangle-free	yes
vertex connectivity	3
vertex count	32
vertex transitive	yes
weakly regular parameters