Dyck graph

Dyck graph
Dyck graph
	The Dyck graph
Named after	W. Dyck
Vertices	32
Edges	48
Radius	5
Diameter	5
Girth	6
Automorphisms	192
Chromatic number	2
Chromatic index	3
Book thickness	3
Queue number	2
Properties	Symmetric; Cubic; Hamiltonian; Bipartite; Cayley graph
	Table of graphs and parameters

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.[1][2]

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.[3]

The Dyck graph is a toroidal graph; the dual of its symmetric toroidal embedding is the Shrikhande graph.

Algebraic properties

The automorphism group of the Dyck graph is a group of order 192.[4] 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.[5]

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 three by twelve octagons, known as the Dyck map or Dyck tiling. The dual graph for this tiling is the complete tripartite graph K_4,4,4.[6][7]

Gallery

Alternative drawing of the Dyck graph.
The chromatic number of the Dyck graph is 2.
The chromatic index of the Dyck graph is 3.

References

Dyck, W. (1881), "Über Aufstellung und Untersuchung von Gruppe und Irrationalität regulärer Riemann'scher Flächen", Math. Ann., 17: 473, doi:10.1007/bf01446929.
Weisstein, Eric W. "Dyck Graph". MathWorld.
Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
Royle, G. F032A data
Conder, M.; Dobcsányi, P. (2002), "Trivalent symmetric graphs up to 768 vertices", J. Combin. Math. Combin. Comput., 40: 41–63.
Dyck, W. (1880), "Notiz über eine reguläre Riemannsche Fläche vom Geschlecht 3 und die zugehörige Normalkurve 4. Ordnung", Math. Ann., 17: 510–516, doi:10.1007/bf01446930.
Ceulemans, A. (2004), "The tetrakisoctahedral group of the Dyck graph and its molecular realization.", Molecular Physics, 102 (11): 1149–1163, doi:10.1080/00268970410001728780.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Dyck, W. (1881), "Über Aufstellung und Untersuchung von Gruppe und Irrationalität regulärer Riemann'scher Flächen", Math. Ann., 17: 473, doi:10.1007/bf01446929.

[2] Weisstein, Eric W. "Dyck Graph". MathWorld.

[3] Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018

[4] Royle, G. F032A data

[5] Conder, M.; Dobcsányi, P. (2002), "Trivalent symmetric graphs up to 768 vertices", J. Combin. Math. Combin. Comput., 40: 41–63.

[6] Dyck, W. (1880), "Notiz über eine reguläre Riemannsche Fläche vom Geschlecht 3 und die zugehörige Normalkurve 4. Ordnung", Math. Ann., 17: 510–516, doi:10.1007/bf01446930.

[7] Ceulemans, A. (2004), "The tetrakisoctahedral group of the Dyck graph and its molecular realization.", Molecular Physics, 102 (11): 1149–1163, doi:10.1080/00268970410001728780.