TOPICS

# 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

Cubic Symmetric Graph, Klein Graph

## Explore with Wolfram|Alpha

More things to try:

## References

Brouwer, A. E. "Dyck Graph." http://www.win.tue.nl/~aeb/drg/graphs/Dyck.html.Dyck, W. "Über Aufstellung und Untersuchung von Gruppe und Irrationalität regulärer Riemann'scher Flächen." Math. Ann. 17, 473, 1881.Gerbracht, E. H.-A. "On the Unit Distance Embeddability of Connected Cubic Symmetric Graphs." Kolloquium über Kombinatorik. Magdeburg, Germany. Nov. 15, 2008.King, R. B. "Novel Highly Symmetrical Trivalent Graphs Which Lead to Negative Curvature Carbon and Boron Nitride Chemical Structures." Disc. Math. 244, 203-210, 2002.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, 1998.

## Cite this as:

Weisstein, Eric W. "Dyck Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DyckGraph.html