In the
mathematical field of
graph theory, the Dyck graph is a 3-
regular graph with 32 vertices and 48 edges, named after
Walther von Dyck.
It is
Hamiltonian with 120 distinct Hamiltonian cycles. It has
chromatic number 2,
chromatic index 3, radius 5, diameter 5 and
girth
Girth may refer to:
;Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* Girth ...
6. It is also a 3-
vertex-connected and a 3-
edge-connected graph. It has
book thickness 3 and
queue number 2.
The Dyck graph is a
toroidal graph
In the mathematical field of graph theory, a toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross.
Examples
Any graph that can be embedded in a plane ...
, and the dual of its symmetric toroidal embedding is the
Shrikhande graph, a strongly regular graph both symmetric and hamiltonian.
Algebraic properties
The automorphism group of the Dyck graph is a group of order 192. It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore, the Dyck graph is a
symmetric graph. It has automorphisms that take any vertex to any other vertex and any edge to any other edge. According to the ''Foster census'', the Dyck graph, referenced as F32A, is the only cubic symmetric graph on 32 vertices.
The
characteristic polynomial
In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The chara ...
of the Dyck graph is equal to
.
Dyck map
The Dyck graph is the
skeleton
A skeleton is the structural frame that supports the body of an animal. There are several types of skeletons, including the exoskeleton, which is the stable outer shell of an organism, the endoskeleton, which forms the support structure inside ...
of a
symmetric tessellation of a surface of
genus three by twelve octagons, known as the Dyck map or Dyck tiling. The
dual graph for this tiling is the
complete tripartite graph ''K''
4,4,4.
[.]
Gallery
Image:Dyck graph.svg, Alternative drawing of the Dyck graph.
Image:Dyck_graph_2COL.svg, The chromatic number of the Dyck graph is 2.
Image:Dyck graph 3color edge.svg, The chromatic index of the Dyck graph is 3.
References
{{reflist
Individual graphs
Regular graphs