Ljubljana graph

Construction

The Ljubljana graph is Hamiltonian and can be constructed from the LCF notation : [47, −23, −31, 39, 25, −21, −31, −41, 25, 15, 29, −41, −19, 15, −49, 33, 39, −35, −21, 17, −33, 49, 41, 31, −15, −29, 41, 31, −15, −25, 21, 31, −51, −25, 23, 9, −17, 51, 35, −29, 21, −51, −39, 33, −9, −51, 51, −47, −33, 19, 51, −21, 29, 21, −31, −39]2.

The Ljubljana graph is the Levi graph of the Ljubljana configuration, a quadrangle-free configuration with 56 lines and 56 points. In this configuration, each line contains exactly 3 points, each point belongs to exactly 3 lines and any two lines intersect in at most one point.

Algebraic properties

The automorphism group of the Ljubljana graph is a group of order 168. It acts transitively on the edges the graph but not on its vertices: there are symmetries taking every edge to any other edge, but not taking every vertex to any other vertex. Therefore, the Ljubljana graph is a semi-symmetric graph, the third smallest possible cubic semi-symmetric graph after the Gray graph on 54 vertices and the Iofinova-Ivanov graph on 110 vertices.

The characteristic polynomial of the Ljubljana graph is :(x-3)x^{14}(x+3)(x^2-x-4)^7(x^2-2)^6(x^2+x-4)^7(x^4-6x^2+4)^{14}.\

History

The Ljubljana graph was first published in 1993 by Brouwer, Dejter and Thomassen as a self-complementary subgraph of the Dejter graph.Klin M.; Lauri J.; Ziv-Av M. "Links between two semisymmetric graphs on 112 vertices through the lens of association schemes", Jour. Symbolic Comput., 47–10, 2012, 1175–1191.

In 1972, Bouwer was already talking of a 112-vertices edge- but not vertex-transitive cubic graph found by R. M. Foster, nonetheless unpublished. Conder, Malnič, Marušič, Pisanski and Potočnik rediscovered this 112-vertices graph in 2002 and named it the Ljubljana graph after the capital of Slovenia. They proved that it was the unique 112-vertices edge- but not vertex-transitive cubic graph and therefore that was the graph found by Foster.

Gallery

Image:Ljubljana_graph_2COL.svg|The Ljubljana graph is Hamiltonian and bipartite Image:Ljubljana_graph_3color_edge.svg|The chromatic index of the Ljubljana graph is 3. Image:Ljubljana graph.svg|Alternative drawing of the Ljubljana graph. Image:Ljubljana configuration.svg|The Ljubljana graph is the Levi graph of this configuration.

References

References

1. [[Marston Conder. Conder, M.]]; Malnič, A.; Marušič, D.; Pisanski, T.; and Potočnik, P. "The Ljubljana Graph." 2002. [http://citeseer.ist.psu.edu/conder02ljubljana.html].
2. "Ljubljana Graph".
3. [[Marston Conder]], Aleksander Malnič, Dragan Marušič and Primož Potočnik. "A census of semisymmetric cubic graphs on up to 768 vertices." Journal of Algebraic Combinatorics: An International Journal. Volume 23, Issue 3, pages 255-294, 2006.
4. Brouwer, A. E.; Dejter, I. J.; and Thomassen, C. "Highly Symmetric Subgraphs of Hypercubes." J. Algebraic Combinat. 2, 25-29, 1993.
5. Bouwer, I. A. "On Edge But Not Vertex Transitive Regular Graphs." J. Combin. Th. Ser. B 12, 32-40, 1972.