Dyck graph
title: "Dyck graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["individual-graphs", "regular-graphs"] topic_path: "general/individual-graphs" source: "https://en.wikipedia.org/wiki/Dyck_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
::data[format=table title="infobox graph"]
| Field | Value |
|---|---|
| name | Dyck graph |
| image | [[Image:Dyck graph hamiltonian.svg |
| image_caption | The Dyck graph |
| namesake | W. Dyck |
| vertices | 32 |
| edges | 48 |
| automorphisms | 192 |
| girth | 6 |
| radius | 5 |
| diameter | 5 |
| chromatic_number | 2 |
| chromatic_index | 3 |
| properties | Symmetric |
| Cubic | |
| Hamiltonian | |
| Bipartite | |
| Cayley graph | |
| book thickness | 3 |
| :: |
| name = Dyck graph | image = [[Image:Dyck graph hamiltonian.svg|250px]] | image_caption = The Dyck graph | namesake = W. Dyck | vertices = 32 | edges = 48 | automorphisms= 192 | girth = 6 | radius = 5 | diameter = 5 | chromatic_number = 2 | chromatic_index = 3 | properties = Symmetric Cubic Hamiltonian Bipartite Cayley graph |book thickness=3|queue number=2}}
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.{{citation | last = Dyck | first = W. | author-link = Walther von Dyck | journal = Math. Ann. | page = 473 | title = Über Aufstellung und Untersuchung von Gruppe und Irrationalität regulärer Riemann'scher Flächen | volume = 17 | year = 1881 | issue = 4 | doi=10.1007/bf01446929| s2cid = 122956853 | url = https://zenodo.org/record/1428238 }}.
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 graph is 1-planar.{{citation | last = Pupyrev | first = Sergey | editor-first1 = Vida | editor-first2 = Fabrizio | editor-last1 = Dujmović | editor-last2 = Montecchiani | contribution = OOPS: Optimized One-Planarity Solver via SAT | doi = 10.4230/LIPIcs.GD.2025.14 | title = Proc. 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) | series = Leibniz International Proceedings in Informatics (LIPIcs) | year = 2025 | volume = 357 | pages = 14:1–14:19 | isbn = 978-3-95977-403-1 | doi-access = free
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.{{citation | last1 = Conder | first1 = M. | author1-link = Marston Conder | last2 = Dobcsányi | first2 = P. | journal = J. Combin. Math. Combin. Comput. | pages = 41–63 | title = Trivalent symmetric graphs up to 768 vertices | volume = 40 | year = 2002}}.
The characteristic polynomial 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, contained in the skeleton of a hexagonal regular map, {6,3}4,0, with 32 vertices, 48 edges, and 16 hexagonal cycles. It is the dual of its symmetric toroidal embedding is the Shrikhande graph.
It can be visualized as net, a 4 by 4 array of hexagons, where left-right and top-bottom wrap into a flat torus. ::data[format=table title="Visualization as regular map and the dual graph regular map"] | Dyck graph on {6,3}4,032 vertices, 48 edges, 16 hexagons||Shrikhande graph on {3,6}4,016 vertices, 48 edges, 32 triangles | |---| | [[File:Regular map 6-3 4-0.png|240px]] | ::
Dyck map
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.{{citation | last = Dyck | first = W. | author-link = Walther von Dyck | journal = Math. Ann. | pages = 510–516 | title = Notiz über eine reguläre Riemannsche Fläche vom Geschlecht 3 und die zugehörige Normalkurve 4. Ordnung | volume = 17 | year = 1880 | doi = 10.1007/bf01446930 | s2cid = 121904710 | url = https://zenodo.org/record/1428240 }}.{{citation | last = Ceulemans | first = A. | doi = 10.1080/00268970410001728780 | issue = 11 | journal = Molecular Physics | pages = 1149–1163 | title = The tetrakisoctahedral group of the Dyck graph and its molecular realization. | volume = 102 | year = 2004| s2cid = 97973403
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
References
- "Dyck Graph".
- Wolz, Jessica; ''Engineering Linear Layouts with SAT.'' Master Thesis, University of Tübingen, 2018
- "G-G".
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::