In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

field of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, the Dyck graph is a 3-

regular graph In graph theory, a regular graph is a Graph (discrete mathematics), graph where each Vertex (graph theory), vertex has the same number of neighbors; i.e. every vertex has the same Degree (graph theory), degree or valency. A regular directed graph ...

with 32 vertices and 48 edges, named after

Walther von Dyck Walther Franz Anton von Dyck (6 December 1856 – 5 November 1934), born Dyck () and later ennobled, was a German mathematician. He is credited with being the first to define a mathematical group, in the modern sense in . He laid the foundation ...

. It is

Hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified Hamiltonian ...

with 120 distinct Hamiltonian cycles. It has

chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

chromatic index In graph theory, a proper edge coloring of a Graph (discrete mathematics), graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge colorin ...

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 In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on ...

3 and queue number 2.

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 In the mathematical field of graph theory, a graph is symmetric or arc-transitive if, given any two ordered pairs of adjacent vertices (u_1,v_1) and (u_2,v_2) of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 a ...

. 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 ...

of the Dyck graph is equal to

(x-3) (x-1)^9 (x+1)^9 (x+3) (x^2-5)^6

Toroidal graph

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 and edges can be placed on a torus such that no edges intersect except at a vertex that belongs to bo ...

, contained in the skeleton of a hexagonal regular map, _4,0, with 32 vertices, 48 edges, and 16 hexagonal cycles. It is the dual of its symmetric toroidal embedding is the

Shrikhande graph In the mathematical field of graph theory, the Shrikhande graph is a graph discovered by S. S. Shrikhande in 1959.. It is a strongly regular graph with 16 vertices and 48 edges, with each vertex having degree 6. Every pair of nodes has ...

. It can be visualized as net, a 4 by 4 array of hexagons, where left-right and top-bottom wrap into a flat torus.

Dyck map

The Dyck graph is the

skeleton A skeleton is the structural frame that supports the body of most animals. There are several types of skeletons, including the exoskeleton, which is a rigid outer shell that holds up an organism's shape; the endoskeleton, a rigid internal fra ...

of a symmetric tessellation of a surface of

genus Genus (; : genera ) is a taxonomic rank above species and below family (taxonomy), family as used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In bino ...

three by twelve octagons, known as the Dyck map or Dyck tiling. The

dual graph In the mathematics, mathematical discipline of graph theory, the dual graph of a planar graph is a graph that has a vertex (graph theory), vertex for each face (graph theory), face of . The dual graph has an edge (graph theory), edge for each p ...

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

of the Dyck graph is 2. Image:Dyck graph 3color edge.svg, The

of the Dyck graph is 3.

References

{{reflist Individual graphs Regular graphs