TOPICS
Search

Jørgensen Graph


JorgensenGraph

The Jørgensen graph is a maximally linklessly embeddable graph on 8 vertices and 21 edges, where "maximal" means it is not a proper subgraph of another linklessly embeddable graph of the same order (Jørgensen 1989, Naimi et al. 2020). It is illustrated above in a number of embeddings.

A family of maximally linklessly embeddable graphs on n vertices and 3n-3 edges may be constructed from this graph by subdividing one of the horizontal edges and adding edges that connect every new vertex to two the top and bottom vertices (Jørgensen 1989, Naimi et al. 2020).


See also

Linklessly Embeddable Graph

Explore with Wolfram|Alpha

References

Jørgensen, L. K. "Some Maximal Graphs That Are Not Contractible to K_6." Report 1989: R 89-28. Aalborg, Denmark: Aalborg Universitetscenter, Institut for Elektroniske Systemer, 1989.Naimi, R.; Pavelescu, A.; and Pavelescu, E. "New Bounds on Maximal Linkless Graphs." 20 Sep 2020. https://arxiv.org/abs/2007.10522.Pierce, M. Fig. 3 in "Searching for and Classifying the Finite Set of Minor-Minimal Non-Apex Graphs." Honours thesis. Chico, CA: California State University, Chico, p. 7, 2014. http://tmattman.yourweb.csuchico.edu/mpthesis.pdf.

Cite this as:

Weisstein, Eric W. "Jørgensen Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/JorgensenGraph.html

Subject classifications