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 Harries graph or Harries (3-10)-cage is a 3-
regular
The term regular can mean normal or in accordance with rules. It may refer to:
People
* Moses Regular (born 1971), America football player
Arts, entertainment, and media Music
* "Regular" (Badfinger song)
* Regular tunings of stringed instrum ...
,
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
with 70
vertices and 105 edges.
The Harries graph 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 o ...
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, blue ...
3, radius 6, diameter 6,
girth 10 and 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 ...
. It is also a 3-
vertex-connected and 3-
edge-connected,
non-planar,
cubic graph
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.
A bicubic graph is a cubic bipa ...
. 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 o ...
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.
Defin ...
2.
The
characteristic polynomial
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 among its coefficients. The ...
of the Harries graph is
:
History
In 1972, A. T. Balaban published a (3-10)-
cage graph
In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.
Formally, an is defined to be a graph in which each vertex has exactly neighbors, and in which the shortest cycle has ...
, a cubic graph that has as few vertices as possible for girth 10. It was the first (3-10)-cage discovered but it was not unique.
The complete list of (3-10)-cage and the proof of minimality was given by O'Keefe and Wong in 1980. There exist three distinct (3-10)-cage graphs—the
Balaban 10-cage, the Harries graph and the
Harries–Wong graph.
[Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.] Moreover, the Harries–Wong graph and Harries graph are
cospectral graphs.
Gallery
Image:Harries graph 2COL.svg, The chromatic number of the Harries graph is 2.
Image:Harries graph 3color edge.svg, The chromatic index of the Harries graph is 3.
Image:harries_graph_alternative_drawing.svg, Alternative drawing of the Harries graph.
Image:Harries graph petersen drawing.jpg, Alternative drawing emphasizing the graph's 4 orbits.
References
{{reflist
Individual graphs
Regular graphs