In
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 Holt graph or Doyle graph is the smallest
half-transitive graph
In the mathematics, mathematical field of graph theory, a half-transitive graph is a Graph (discrete mathematics), graph that is both Vertex-transitive graph, vertex-transitive and Edge-transitive graph, edge-transitive, but not symmetric graph, s ...
, that is, the smallest example of a
vertex-transitive
In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of face i ...
and
edge-transitive
In geometry, a polytope (for example, a polygon or a polyhedron) or a Tessellation, tiling is isotoxal () or edge-transitive if its Symmetry, symmetries act Transitive group action, transitively on its Edge (geometry), edges. Informally, this mea ...
graph which is not also
symmetric
Symmetry () in everyday life refers to a sense of harmonious and beautiful proportion and balance. In mathematics, the term has a more precise definition and is usually used to refer to an object that is invariant under some transformations ...
. 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.
The Holt graph has
diameter
In geometry, a diameter of a circle is any straight line segment that passes through the centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...
3, radius 3 and
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 ...
5,
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 ...
3,
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 ...
5 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 ...
with distinct Hamiltonian cycles.
It is also a 4-
vertex-connected and a 4-
edge-connected graph. It has
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 ...
3 and
queue number 3.
[Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018]
It has an
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 order 54.
This is a smaller group than a symmetric graph with the same number of vertices and edges would have. The graph drawing on the right highlights this, in that it lacks reflectional symmetry.
The characteristic polynomial of the Holt graph is
:
Gallery
Image:Holt graph 3COL.svg, The 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 ...
of the Holt graph is 3.
Image:Holt graph 5color edge.svg, The 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 ...
of the Holt graph is 5.
Image:Holt graph hamiltonian.svg, The Holt graph 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 ...
.
File:Holt graph unit distance.svg, The Holt graph is a unit distance graph.
References
{{reflist
Individual graphs
Regular graphs