TOPICS
Search

Lindgren-Sousselier Graph


LindgrenSousselierGraphs

The Lindgren-Sousselier graphs are a sequence of hypohamiltonian graphs with 6k+4 vertices independently discovered by Sousselier (in Herz et al. 1967) and Lindgren (1967) for k=1, 2, ..., the first few of which are illustrated above. 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.


See also

Hypohamiltonian Graph, Petersen Graph

Explore with Wolfram|Alpha

References

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:

Weisstein, Eric W. "Lindgren-Sousselier Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Lindgren-SousselierGraph.html

Subject classifications