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 |