In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

field of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, the Horton graph or Horton 96-graph is a 3-

regular graph In graph theory, a regular graph is a Graph (discrete mathematics), graph where each Vertex (graph theory), vertex has the same number of neighbors; i.e. every vertex has the same Degree (graph theory), degree or valency. A regular directed 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 mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...

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

. 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 methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

chromatic index In graph theory, a proper edge coloring of a Graph (discrete mathematics), 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 colorin ...

3, radius 10, diameter 10,

girth Girth may refer to: Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * Girth ...

book thickness In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in 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 on ...

3Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018 and

queue number In the mathematical field of graph theory, the queue number of a Graph (discrete mathematics), graph is a graph invariant defined analogously to book thickness, stack number (book thickness) using Queue (abstract data type), first-in first-out (q ...

2. It is also a 3- edge-connected graph.

Algebraic properties

The

automorphism group In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...

of the Horton graph is of order 96 and is isomorphic to Z/2Z×Z/2Z×''S''₄, the

direct product In mathematics, a direct product of objects already known can often be defined by giving a new one. That induces a structure on the Cartesian product of the underlying sets from that of the contributing objects. The categorical product is an abs ...

of the

Klein four-group In mathematics, the Klein four-group is an abelian group with four elements, in which each element is Involution (mathematics), self-inverse (composing it with itself produces the identity) and in which composing any two of the three non-identi ...

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

''S''₄. 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 :

(x-3) (x-1)^ x^4 (x+1)^ (x+3) (x^2-5)^3 (x^2-3)^(x^2-x-3) (x^2+x-3)

(x^-23 x^8+188 x^6-644 x^4+803 x^2-101)^2

(x^-20 x^8+143 x^6-437 x^4+500 x^2-59)

Gallery

Image:Horton graph 2COL.svg, The

of the Horton graph is 2. Image:Horton graph 3color edge.svg, The

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