The Sousselier graph is, in
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 ...
, a
hypohamiltonian graph
In the mathematical field of graph theory, a graph ''G'' is said to be hypohamiltonian if ''G'' itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from ''G'' is Hamiltonian.
History
Hypohamiltonian graphs ...
with 16 vertices and 27 edges. 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.
History
Hypohamiltonian graphs were first studied by Sousselier in ''Problèmes plaisants et délectables'' (1963)
.
In 1967, Lindgren builds an infinite sequence of hypohamiltonian graphs.
The graphs of this sequence all have 6''k''+10 vertices, for every integer ''k''.
The same sequence of hypohamiltonian graphs is independently built by Sousselier.
[
] In 1973
Chvátal explains in a scientific paper how edges can be added to some hypohamiltonian graphs in order to build new ones of the same order, and he names Bondy
as the original author of the method. As an illustration, he shows that two edges can be added to the second graph of the Lindgren sequence (which he names Sousselier sequence) in order to build a new hypohamiltonian graph on 16 vertices. This graph is named the Sousselier graph.
References
{{Reflist
Individual graphs