In the mathematical

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 field of graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, the Ljubljana graph is an undirected bipartite graph

Bipartite graph

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

 with 112 vertices

Vertex (graph theory)

In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...

 and 168 edges.

It is a cubic graph

Cubic graph

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....

 with diameter 8, radius 7, chromatic number 2 and chromatic index 3. Its girth is 10 and there are exactly 168 cycles of length 10 in it. There are also 168 cycles of length 12.

Construction

The Ljubljana graph is Hamiltonian and can be constructed from the LCF notation

LCF notation

In combinatorial mathematics, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by Coxeter and Frucht, for the representation of cubic graphs that are Hamiltonian. Since the graphs are Hamiltonian, the vertices can be arranged in a cycle, which accounts for two edges...

 : [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]².

The Ljubljana graph is the Levi graph

Levi graph

In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure. From a collection of points and lines in an incidence geometry or a projective configuration, we form a graph with one vertex per point, one vertex per line, and an edge for...

 of the Ljubljana configuration, a quadrangle-free configuration with 56 lines and 56 points. In this configuration, each line contains exactly 3 points, each points 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

Graph automorphism

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity....

 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

Semi-symmetric graph

In the mathematical field of graph theory, a semi-symmetric graph is an undirected graph that is edge-transitive and regular, but not vertex-transitive....

, the third smallest possible cubic semi-symmetric graph after the Gray graph

Gray graph

In the mathematical field of graph theory, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. It was discovered by Marion C. Gray in 1932 , then discovered independently by Bouwer 1968 in reply to a question...

 on 54 vertices and the Iofinova-Ivanov graph on 110 vertices.

The characteristic polynomial of the Ljubljana graph is

History

The Ljubljana graph was first published in 1993 by Brouwer

Andries Brouwer

Andries Evert Brouwer is a Dutch mathematician and computer programmer, a professor at Eindhoven University of Technology . His varied research interests include several branches of discrete mathematics, particularly graph theory and coding theory...

, Dejter and Thomassen

Carsten Thomassen

Carsten Thomassen is a Danish mathematician. He has been a Professor of Mathematics at the Technical University of Denmark since 1981, and since 1990 a member of the Royal Danish Academy of Sciences and Letters. His research concerns discrete mathematics and more specifically graph...

.

In 1972, Bouwer was already talking of a 112-vertices edge- but not vertex-transitive cubic graph found by R. M. Foster

R. M. Foster

Ronald Martin Foster , was a Bell Labs mathematician whose work was of significance regarding electronic filters for use on telephone lines...

, but unpublished. Conder, Malnič, Marušič, Pisanski and Potočnik rediscovered this 112-vertices graph in 2002 and named it the Ljubljana

Ljubljana

Ljubljana is the capital of Slovenia and its largest city. It is the centre of the City Municipality of Ljubljana. It is located in the centre of the country in the Ljubljana Basin, and is a mid-sized city of some 270,000 inhabitants...

 graph after the capital of Slovenia

Slovenia

Slovenia , officially the Republic of Slovenia , is a country in Central and Southeastern Europe touching the Alps and bordering the Mediterranean. Slovenia borders Italy to the west, Croatia to the south and east, Hungary to the northeast, and Austria to the north, and also has a small portion of...

. 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.