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

Last updated June 09, 2019

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]

Mathematics Field of study concerning quantity, patterns and change

Mathematics includes the study of such topics as quantity, structure, space, and change.

Graph theory Area of discrete mathematics

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 which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

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 outdegree of each vertex are equal to each other. A regular graph with vertices of degree $k$ is called a $k$ ‑regular graph or regular graph of degree $k$ . Also, from the handshaking lemma, a regular graph of odd degree will contain an even number of vertices.

In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles, its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free.

In graph theory, a connected graph G is said to be k-vertex-connected if it has more than k vertices and remains connected whenever fewer than k vertices are removed.

In graph theory, a connected graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.

The Dyck graph is a toroidal graph, and the dual of its symmetric toroidal embedding is the Shrikhande graph, a strongly regular graph both symmetric and hamiltonian.

Toroidal graph node-link graph that can be embedded on a torus

In mathematics, 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.

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 has exactly two other neighbors in common, whether the pair of nodes is connected or not.

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]

In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u₁—v₁ and u₂—v₂ of G, there is an automorphism

The characteristic polynomial of the Dyck graph is equal to $(x-3)(x-1)^{9}(x+1)^{9}(x+3)(x^{2}-5)^{6}$ .

In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix as coefficients. The characteristic polynomial of an endomorphism of vector spaces of finite dimension is the characteristic polynomial of the matrix of the endomorphism over any base; it does not depend on the choice of a basis. The characteristic equation is the equation obtained by equating to zero the characteristic polynomial.

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]

In mathematics, a regular map is a symmetric tessellation of a closed surface. More precisely, a regular map is a decomposition of a two-dimensional manifold into topological disks such that every flag can be transformed into any other flag by a symmetry of the decomposition. Regular maps are, in a sense, topological generalizations of Platonic solids. The theory of maps and their classification is related to the theory of Riemann surfaces, hyperbolic geometry, and Galois theory. Regular maps are classified according to either: the genus and orientability of the supporting surface, the underlying graph, or the automorphism group.

In the mathematical discipline of graph theory, the dual graph of a plane graph $G$ is a graph that has a vertex for each face of $G$ . The dual graph has an edge whenever two faces of $G$ are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge $e$ of $G$ has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of $e$ . The definition of the dual depends on the choice of embedding of the graph $G$ , so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.

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.

Related Research Articles

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.

In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.

In the mathematical field of graph theory, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. It was discovered by Marion C. Gray in 1932 (unpublished), then discovered independently by Bouwer 1968 in reply to a question posed by Jon Folkman 1967. The Gray graph is interesting as the first known example of a cubic graph having the algebraic property of being edge but not vertex transitive.

In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 cubic distance-regular graphs are known. It is named after Harold Scott MacDonald Coxeter.

In the mathematical field of graph theory, the Pappus graph is a bipartite 3-regular undirected graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration. It is named after Pappus of Alexandria, an ancient Greek mathematician who is believed to have discovered the "hexagon theorem" describing the Pappus configuration. All the cubic distance-regular graphs are known; the Pappus graph is one of the 13 such graphs.

In the mathematical field of graph theory, the Foster graph is a bipartite 3-regular graph with 90 vertices and 135 edges.

In the mathematical field of graph theory, the Möbius–Kantor graph is a symmetric bipartite cubic graph with 16 vertices and 24 edges named after August Ferdinand Möbius and Seligmann Kantor. It can be defined as the generalized Petersen graph G(8,3): that is, it is formed by the vertices of an octagon, connected to the vertices of an eight-point star in which each point of the star is connected to the points three steps away from it.

In the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph.

In the mathematical field of graph theory, the Franklin graph a 3-regular graph with 12 vertices and 18 edges.

In the mathematical field of graph theory, the Folkman graph, named after Jon Folkman, is a bipartite 4-regular graph with 20 vertices and 40 edges.

In the mathematical field of graph theory, the Biggs–Smith graph is a 3-regular graph with 102 vertices and 153 edges.

In the mathematical field of graph theory, the Nauru graph is a symmetric bipartite cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.

In the mathematical field of graph theory, the F26A graph is a symmetric bipartite cubic graph with 26 vertices and 39 edges.

In the mathematical field of graph theory, the Robertson graph or (4,5)-cage, is a 4-regular undirected graph with 19 vertices and 38 edges named after Neil Robertson.

In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges.

In the mathematical field of graph theory, the Hoffman graph is a 4-regular graph with 16 vertices and 32 edges discovered by Alan Hoffman. Published in 1963, it is cospectral to the hypercube graph Q₄.

In the mathematical field of graph theory, the Holt graph or Doyle graph is the smallest half-transitive graph, that is, the smallest example of a vertex-transitive and edge-transitive graph which is not also symmetric. Such graphs are not common. It is named after Peter G. Doyle and Derek F. Holt, who discovered the same graph independently in 1976 and 1981 respectively.

In the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges named after W. T. Tutte.

In the mathematical field of graph theory, the Klein graphs are two different but related regular graphs, each with 84 edges. Each can be embedded in the orientable surface of genus 3, in which they form dual graphs.

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 page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

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