In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, the Ljubljana graph is an

undirected In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

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

with 112 vertices and 168 edges. It is a

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. A bicubic graph is a cubic bipa ...

with diameter 8, radius 7,

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

2 and

chromatic index In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...

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 Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified Hamiltonian ...

and can be constructed from the

LCF notation In the mathematical field of graph theory, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by H. S. M. Coxeter and Robert Frucht, for the representation of cubic graphs that contain a Hamiltonian cycle. The cycle ...

: [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 In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure.. See in particulap. 181 From a collection of points and lines in an incidence geometry or a projective configuration, we form ...

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 In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...

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 Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...

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 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. In other words, a graph is semi-symmetric if each vertex has the same number of incident edg ...

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

Gray graph Grey (more common in British English) or gray (more common in American English) is an intermediate color between black and white. It is a neutral or achromatic color, meaning literally that it is "without color", because it can be composed o ...

on 54 vertices and the Iofinova-Ivanov graph on 110 vertices. The characteristic polynomial of the Ljubljana graph is :

(x-3)x^(x+3)(x^2-x-4)^7(x^2-2)^6(x^2+x-4)^7(x^4-6x^2+4)^.\

History

The Ljubljana graph was first published in 1993 by

Brouwer Brouwer (also Brouwers and de Brouwer) is a Dutch and Flemish surname. The word ''brouwer'' means 'beer brewer'. Brouwer * Adriaen Brouwer (1605–1638), Flemish painter * Alexander Brouwer (b. 1989), Dutch beach volleyball player * Andries Bro ...

, Dejter and

Thomassen Thomassen is a patronymic family name of Scandinavian and Dutch origin. It literally means "son of Thomas", i.e., approximately corresponds to Thomson. Notable people with the name include: * Ann-Mari Thomassen (born 1964), Sámi politician * Bj ...

as a self-complementary subgraph of the

Dejter graph In the mathematics, mathematical field of graph theory, the Dejter graph is a 6-regular graph with 112 vertices and 336 edges.Borges J.; Dejter I. J. "On perfect dominating sets in hypercubes and their complements", J. Combin. Math. Combin. Com ...

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

R. M. Foster Ronald Martin Foster (3 October 1896 – 2 February 1998), was a Bell Labs mathematician whose work was of significance regarding electronic filters for use on telephone lines. He published an important paper, ''A Reactance Theorem'', (see Foster ...

, nonetheless unpublished.Bouwer, I. A. "On Edge But Not Vertex Transitive Regular Graphs." J. Combin. Th. Ser. B 12, 32-40, 1972. Conder, Malnič, Marušič, Pisanski and Potočnik rediscovered this 112-vertices graph in 2002 and named it the

Ljubljana Ljubljana (also known by other historical names) is the capital and largest city of Slovenia. It is the country's cultural, educational, economic, political and administrative center. During antiquity, a Roman city called Emona stood in the ar ...

graph after the capital of

Slovenia Slovenia ( ; sl, Slovenija ), officially the Republic of Slovenia (Slovene: , abbr.: ''RS''), is a country in Central Europe. It is bordered by Italy to the west, Austria to the north, Hungary to the northeast, Croatia to the southeast, an ...

. Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; and Potočnik, P. "The Ljubljana Graph." 2002

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

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

of this configuration.

References

{{reflist Individual graphs Regular graphs