TOPICS
Search

Lindgren-Sousselier Graphs


The Lindgren-Sousselier graphs are a sequence of hypohamiltonian graphs on 6k+4 vertices independently discovered by Sousselier (Herz et al. 1967) and Lindgren (1967). However, according to correspondence between V. Chvátal and D. E. Knuth in the mid-2020's, Berge (1970, p. 214) contains a footnote which mentions that Sousselier wrote Berge on Jan. 6, 1963 stating, "this [result] stems from a property that I discovered 31 years ago and never published." It therefore appears that Sousslier constructed (but did not publish) the Lindgren-Sousselier graphs as early as 1932 (D. E. Knuth, pers. comm., Feb. 6, 2026).

LindgrenSousselierGraphs

The first Lindgren-Sousselier graphs are illustrated above for k=1, 2, ..., where, in this indexing convention, the graph with k=1 is the Petersen graph.

LindgrenSousselierGraph28

A number of different embeddings of the Lindgren-Sousselier graph on 28 vertices are illustrated above.

The Lindgren-Sousselier graph indexed by k has graph crossing number and rectilinear crossing number k+1 and local crossing number 1. The Lindgren-Sousselier graphs are therefore nonplanar 1-planar graphs.

The Lindgren-Sousselier graphs are platypus graphs.


See also

Hypohamiltonian Graph, Petersen Graph, Sousselier Graph

Portions of this entry contributed by Don Knuth

Explore with Wolfram|Alpha

References

Berge, C. Graphes et Hypergraphes. Paris: Dunod, 1970.Herz, J. C.; Duby, J. J.; and Vigué, F. "Recherche systématique des graphes hypohamiltoniens." In Theory of Graphs: Internat. Sympos., Rome 1966 (Ed. P. Rosenstiehl). Paris: Gordon and Breach, pp. 153-159, 1967.Lindgren, W. F. "An Infinite Class of Hypohamiltonian Graphs." Amer. Math. Monthly 74, 1087-1089, 1967.

Cite this as:

Knuth, Don and Weisstein, Eric W. "Lindgren-Sousselier Graphs." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Lindgren-SousselierGraphs.html

Subject classifications