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 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; the dual of its symmetric toroidal embedding is the Shrikhande graph.
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 of the Dyck graph is equal to .
The Dyck graph is the skeleton 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 K4,4,4.
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.
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
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 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; the dual of its symmetric toroidal embedding is the Shrikhande graph.
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 a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.