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
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 outdegr ...
with 16 vertices and 32 edges discovered by
Alan Hoffman. Published in 1963, it is cospectral to the
hypercube graph
In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube.
has vertices, e ...
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 ...
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, blu ...
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
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into 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 ...
3 and
queue number
In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings.
Defi ...
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 bina ...
Z/2Z.
The
characteristic polynomial of the Hoffman graph is equal to
:
making it an
integral graph In the mathematical field of graph theory, an integral graph is a graph whose adjacency matrix's spectrum consists entirely of integers. In other words, a graph is an integral graph if all of the roots of the characteristic polynomial of its adjace ...
—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 colors ...
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 ...
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, blu ...
of the Hoffman graph is 4.
References
{{reflist
Individual graphs
Regular graphs