TOPICS
Search

Dyck Graph


DyckGraphEmbeddings

The Dyck graph is unique cubic symmetric graph on 32 nodes, illustrated above in a number of embeddings. It is denoted F_(032)A 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"].

DyckGraphUnitDistance

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

DyckGraphLCF

The Dyck graph can be represented in LCF notation as [-13,5,-5,13]^8, [-13,-11,-5,13,-13,5,11,13]^4, and [9,-9,-7,7,9,-9,9,-9]^4, illustrated above.

DyckGraph3D

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.

DyckGraphMatrices

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

The Dyck graph has graph spectrum

 (-3)^1(-sqrt(5))^6(-1)^91^9(sqrt(5))^63^1.

The following table summarizes some properties of the Dyck graph.

propertyvalue
automorphism group order192
characteristic polynomial(x-3)(x-1)^9(x+1)^9(x+3)(x^2-5)^6
chromatic number2
chromatic polynomial?
claw-freeno
clique number2
graph complement name?
determined by spectrumno
diameter5
distance-regular graphno
dual graph nameShrikhande graph
edge chromatic number3
edge connectivity3
edge count48
edge transitiveyes
Eulerianno
girth6
Hamiltonianyes
Hamiltonian cycle count120
Hamiltonian path count?
integral graphno
independence number16
line graphno
perfect matching graphno
planarno
polyhedral graphno
radius5
regularyes
square-freeyes
symmetricyes
traceableyes
triangle-freeyes
vertex connectivity3
vertex count32
vertex transitiveyes
weakly regular parameters(32,(3),(0),(0,1))

See also

Cubic Symmetric Graph, Klein Graph

Explore with Wolfram|Alpha

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

Subject classifications