TOPICS
Search

Ljubljana Graph


LjubljanaGraph

The Ljubljana graph is a graph on 112 vertices that is the third smallest cubic semisymmetric graph. It was discovered by Brouwer et al. (1993) and rediscovered by Conder et al. (2002), but appears to have been known by R. M. Foster based on the comment, "R. M. Foster (private communication) has found an edge- but not vertex-transitive cubic graph (with 112 vertices) whose girth (equal to 10) is not a multiple of 4" appearing in Bouwer (1972).

LjubljanaGraphLCF

It is illustrated above in a number of embeddings having order-2 LCF notation.

The only cubic semisymmetric graphs on smaller numbers of vertices are the Gray graph on 54 vertices and the Iofinova-Ivanov graph on 110 vertices.

It is related to the Dejter graph.


See also

Cubic Semisymmetric Graph, Dejter Graph, Gray Graph, Iofinova-Ivanov Graphs, Semisymmetric Graph

Explore with Wolfram|Alpha

References

Bouwer, I. A. "On Edge But Not Vertex Transitive Regular Graphs." J. Combin. Th. Ser. B 12, 32-40, 1972.Brouwer, A. E.; Dejter, I. J.; and Thomassen, C. "Highly Symmetric Subgraphs of Hypercubes." J. Algebraic Combinat. 2, 25-29, 1993.Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; and Potočnik, P. "The Ljubljana Graph." 2002. http://citeseer.ist.psu.edu/conder02ljubljana.html.

Cite this as:

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

Subject classifications