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).
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.
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 GraphPortions of this entry contributed by Don Knuth
Explore with Wolfram|Alpha
More things to try:
References
Berge, C. Graphes et Hypergraphes. Paris, France: 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, France: Gordon and Breach, pp. 153-159, 1967.House of Graphs. Lindgren-Sousselier Graphs. Lindgren-Sousselier Graph 2, Lindgren-Sousselier Graph 3, and Petersen Graph.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