Ljubljana Graph
   HOME

TheInfoList



OR:

In the
mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
field of
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, the Ljubljana graph is an
undirected In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
with 112 vertices and 168 edges, rediscovered in 2002 and named after
Ljubljana {{Infobox settlement , name = Ljubljana , official_name = , settlement_type = Capital city , image_skyline = {{multiple image , border = infobox , perrow = 1/2/2/1 , total_widt ...
(the capital of
Slovenia Slovenia, officially the Republic of Slovenia, is a country in Central Europe. It borders Italy to the west, Austria to the north, Hungary to the northeast, Croatia to the south and southeast, and a short (46.6 km) coastline within the Adriati ...
). Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; and Potočnik, P. "The Ljubljana Graph." 2002

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 bip ...
with diameter 8, radius 7,
chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...
2 and
chromatic index In graph theory, a proper edge coloring of a Graph (discrete mathematics), 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 colorin ...
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 : [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 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 ...
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 () in everyday life refers to a sense of harmonious and beautiful proportion and balance. In mathematics, the term has a more precise definition and is usually used to refer to an object that is invariant under some transformations ...
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 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, Dejter and
Thomassen Thomassen is a patronymic A patronymic, or patronym, is a component of a personal name based on the given name of one's father, grandfather (more specifically an avonymic), or an earlier male ancestor. It is the male equivalent of a matronymic ...
as a self-complementary subgraph of the Dejter graph. In 1972, Bouwer was already talking of a 112-vertices edge- but not vertex-transitive cubic graph found by R. M. 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 {{Infobox settlement , name = Ljubljana , official_name = , settlement_type = Capital city , image_skyline = {{multiple image , border = infobox , perrow = 1/2/2/1 , total_widt ...
graph after the capital of
Slovenia Slovenia, officially the Republic of Slovenia, is a country in Central Europe. It borders Italy to the west, Austria to the north, Hungary to the northeast, Croatia to the south and southeast, and a short (46.6 km) coastline within the Adriati ...
. 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
chromatic index In graph theory, a proper edge coloring of a Graph (discrete mathematics), 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 colorin ...
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 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 ...
of this configuration.


References

{{reflist Individual graphs Regular graphs