Horton graph
Encyclopedia
In the mathematical
field of graph theory
, 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
3-connected bipartite graph
is Hamiltonian.
After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found. Among them are a 92 vertices graph by Horton published in 1982, a 78 vertices graph by Owens published in 1983, and the two Ellingham-Horton graph
s (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 know counterexample to the Tutte conjecture. The second one was published by Ellingham and Horton in 1983 and was of order 54. No smaller non-hamiltonian cubic 3-connected bipartite graph is currently known.
As a non-hamiltonian cubic graph with many long cycles, the Horton graph provides good benchmark for programs that search for Hamiltonian cycles.
The Horton graph has chromatic number 2, chromatic index 3, radius 10, diameter 10 and girth 6. It is also a 3-edge-connected graph
.
of the Horton graph is of order 96 and is isomorphic to Z/2Z×Z/2Z×S4, the direct product of the cyclic group
Z/2Z with itself and the symmetric group
S4.
The characteristic polynomial
of the Horton graph is :
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the Horton graph or Horton 96-graph is a 3-regular graph
Regular graph
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...
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 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....
3-connected bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
is Hamiltonian.
After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found. Among them are a 92 vertices graph by Horton published in 1982, a 78 vertices graph by Owens published in 1983, and the two Ellingham-Horton graph
Ellingham-Horton graph
In the mathematical field of graph theory, the Ellingham–Horton graphs are two 3-regular graphs on 54 and 78 vertices : the Ellingham–Horton 54-graph and the Ellingham–Horton 78-graph. They are named after Joseph D. Horton and Mark N. Ellingham, their discoverers. These two graphs provide...
s (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 know counterexample to the Tutte conjecture. The second one was published by Ellingham and Horton in 1983 and was of order 54. No smaller non-hamiltonian cubic 3-connected bipartite graph is currently known.
As a non-hamiltonian cubic graph with many long cycles, the Horton graph provides good benchmark for programs that search for Hamiltonian cycles.
The Horton graph has chromatic number 2, chromatic index 3, radius 10, diameter 10 and girth 6. It is also a 3-edge-connected graph
K-edge-connected graph
In graph theory, a graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.-Formal definition:Let G = be an arbitrary graph....
.
Algebraic properties
The automorphism groupGraph automorphism
In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity....
of the Horton graph is of order 96 and is isomorphic to Z/2Z×Z/2Z×S4, the direct product of the cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
Z/2Z with itself and the symmetric group
Symmetric group
In mathematics, the symmetric group Sn on a finite set of n symbols is the group whose elements are all the permutations of the n symbols, and whose group operation is the composition of such permutations, which are treated as bijective functions from the set of symbols to itself...
S4.
The characteristic polynomial
Characteristic polynomial
In linear algebra, one associates a polynomial to every square matrix: its characteristic polynomial. This polynomial encodes several important properties of the matrix, most notably its eigenvalues, its determinant and its trace....
of the Horton graph is :
.