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 Hoffman graph is a 4-
regular graph with 16 vertices and 32 edges discovered by
Alan Hoffman. Published in 1963, it is cospectral to the
hypercube graph Q
4.
The Hoffman graph has many common properties with the hypercube Q
4—both are
Hamiltonian and have
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 ...
4, girth 4 and diameter 4. It is also a 4-
vertex-connected graph and a 4-
edge-connected graph. However, it is not
distance-regular. It has
book thickness 3 and
queue number 2.
[Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018]
Algebraic properties
The Hoffman graph is not a
vertex-transitive graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism
:f : G \to G\
such that
:f(v_1) = v_2.\
In other words, a graph is vertex-transitive ...
and its full automorphism group is a group of order 48 isomorphic to the
direct product of 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 and the
cyclic group
In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bi ...
Z/2Z.
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 Hoffman graph is equal to
:
making it an
integral graph—a graph whose
spectrum
A spectrum (plural ''spectra'' or ''spectrums'') is a condition that is not limited to a specific set of values but can vary, without gaps, across a continuum. The word was first used scientifically in optics to describe the rainbow of color ...
consists entirely of integers. It is the same spectrum as the hypercube Q
4.
Gallery
Image:Hoffman graph hamiltonian.svg, The Hoffman graph is Hamiltonian.
Image:Hoffman 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 Hoffman graph is 2.
Image:Hoffman graph 4color 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 Hoffman graph is 4.
References
{{reflist
Individual graphs
Regular graphs