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 ...
2,
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
.
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 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 ...
of the Dyck graph is 2.
Image:Dyck graph 3color edge.svg, The 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 ...
of the Dyck graph is 3.
References
{{reflist
Individual graphs
Regular graphs