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 Horton graph or Horton 96-graph is a 3-
regular graph with 96 vertices and 144 edges discovered by Joseph Horton. Published by Bondy and Murty in 1976, it provides a counterexample to the Tutte conjecture that every
cubic
Cubic may refer to:
Science and mathematics
* Cube (algebra), "cubic" measurement
* Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex
** Cubic crystal system, a crystal system w ...
3-connected
bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...
is
Hamiltonian.
After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found. Among them are a 92 vertex graph by Horton published in 1982, a 78 vertex graph by Owens published in 1983, and the two
Ellingham-Horton graphs (54 and 78 vertices).
The first Ellingham-Horton graph was published by Ellingham in 1981 and was of order 78. At that time, it was the smallest known counterexample to the Tutte conjecture. The second one was published by Ellingham and Horton in 1983 and was of order 54. In 1989, Georges' graph, the smallest currently-known non-Hamiltonian 3-connected cubic bipartite graph was discovered, containing 50 vertices.
As a non-Hamiltonian cubic graph with many long cycles, the Horton graph provides good benchmark for programs that search for Hamiltonian cycles.
[V. Ejov, N. Pugacheva, S. Rossomakhine, P. Zograf "An effective algorithm for the enumeration of edge colorings and Hamiltonian cycles in cubic graphs]
arXiv:math/0610779v1
The Horton 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 10, diameter 10,
girth 6,
book thickness 3
[Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018] and
queue number 2.
It is also a 3-
edge-connected graph.
Algebraic properties
The
automorphism group of the Horton graph is of order 96 and is isomorphic to Z/2Z×Z/2Z×''S''
4, the
direct product of the
Klein four-group and the
symmetric group
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group ...
''S''
4.
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 Horton graph is :
.
Gallery
Image:Horton graph 2COL.svg, The 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 ...
of the Horton graph is 2.
Image:Horton graph 3color edge.svg, The 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 ...
of the Horton graph is 3.
Image:Ellingham-Horton 54-graph.svg, The Ellingham-Horton 54-graph, a smaller counterexample to the Tutte conjecture.
References
{{reflist
Individual graphs
Regular graphs