In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the Dyck graph is a 3-

regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegr ...

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

. 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 special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

chromatic index In graph theory, an edge coloring of a 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 coloring of a graph by the colors red, blu ...

3, radius 5, diameter 5 and 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 into 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 ...

3 and

queue number In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings. Defi ...

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 In the mathematical field of graph theory, the Shrikhande graph is a named 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 h ...

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

. 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 of the Dyck graph is equal to

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

Dyck map

The Dyck graph is the skeleton of a symmetric tessellation of a surface of

genus Genus ( plural genera ) is a taxonomic rank used in the biological classification of living and fossil organisms as well as viruses. In the hierarchy of biological classification, genus comes above species and below family. In binomial nom ...

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

dual graph In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-lo ...

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