Template:Infobox graph In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges.^[1]

It is a cubic graph 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.^[2]

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

The Ljubljana graph is the Levi graph of the Ljubljana configuration, a quadrangle-free configuration with 56 lines and 56 points.^[2] 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 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.^[3]

The characteristic polynomial of the Ljubljana graph is

${\displaystyle (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^[4] as a self-complementary subgraph of the Dejter graph. ^[5]

In 1972, Bouwer was already talking of a 112-vertices edge- but not vertex-transitive cubic graph found by R. M. Foster, nonetheless unpublished.^[6] 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.^[2] 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

• 

  The chromatic number of the Ljubljana graph is 2.

• 

  The chromatic index of the Ljubljana graph is 3.

• 

  Alternative drawing of the Ljubljana graph.

• 

  The Ljubljana graph is the Levi graph of this configuration.

• 

  The Ljubljana graph with a Heawood graph embedding.

References

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

File:The graph y = √x(s).svg is a vector version of this file. It should be used in place of this PNG file when not inferior. File:The graph y = √x(s).png → File:The graph y = √x(s).svg For more information, see Help:SVG. In other languages Alemannisch ∙ Bahasa Indonesia ∙ Bahasa Melayu ∙ British English ∙ català ∙ čeština ∙ dansk ∙ Deutsch ∙ eesti ∙ English ∙ español ∙ Esperanto ∙ euskara ∙ français ∙ Frysk ∙ galego ∙ hrvatski ∙ Ido ∙ italiano ∙ lietuvių ∙ magyar ∙ Nederlands ∙ norsk bokmål ∙ norsk nynorsk ∙ occitan ∙ Plattdüütsch ∙ polski ∙ português ∙ português do Brasil ∙ română ∙ Scots ∙ sicilianu ∙ slovenčina ∙ slovenščina ∙ suomi ∙ svenska ∙ Tiếng Việt ∙ Türkçe ∙ vèneto ∙ Ελληνικά ∙ беларуская (тарашкевіца) ∙ български ∙ македонски ∙ нохчийн ∙ русский ∙ српски / srpski ∙ татарча/tatarça ∙ українська ∙ ქართული ∙ հայերեն ∙ বাংলা ∙ தமிழ் ∙ മലയാളം ∙ ไทย ∙ 한국어 ∙ 日本語 ∙ 简体中文 ∙ 繁體中文 ∙ עברית ∙ العربية ∙ فارسی ∙ +/−

 

Summary

DescriptionThe graph y = √x(s).png	English: The graph y = ${\displaystyle {\sqrt {x}}_{s}}$.
Date	25 August 2009, 11:34 (UTC)
Source	Own work (Original text: I (Robo37 (talk)) created this work entirely by myself.)
Author	Robo37 (talk)

Licensing

This work has been released into the public domain by its author, Robo37 at English Wikipedia. This applies worldwide. In some countries this may not be legally possible; if so: Robo37 grants anyone the right to use this work for any purpose, without any conditions, unless such conditions are required by law.Public domainPublic domainfalsefalse

Original upload log