Ljubljana (graf)

Ljubljana
Ljubljana je Hamiltonov graf.
Ime	Ljubljana
Točke	112
Povezave	168
Polmer	7
Premer	8
Notranji obseg	10
Avtomorfizem	168
Kromatično število	2
Kromatični indeks	3
Značilnosti	kubičen regularen dvodelen polsimetričen Hamiltonov
Označba	$\mathcal{L}\!\,$

Ljubljana je v teoriji grafov neusmerjeni dvodelni graf s 112 točkami in 168 povezavami.

Je kubični graf s premerom 8, polmerom 7, kromatičnim številom 2 in kromatičnim indeksom 3. Njegov notranji obseg je 10, v njem pa je točno $2^{3}\cdot 3\cdot 7 = 168$ ciklov dolžine 10. Graf ima tudi 168 ciklov dolžine 12.

Konstrukcija

Ljubljana je Hamiltonov graf in ga lahko skonstruiramo iz zapisa LCF : [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]².

Ljubljana je Levijev graf s konfugracijo Ljubljana, konfiguracijo brez pravih kotov s 56 daljicami in 56 točkami. V takšni konfiguraciji vsaka daljica vsebuje točno 3 točke, vsaka točka pripada točno 3 daljicam in poljubni par daljic se seka v samo eni točki.

Algebrske značilnosti

Grupa avtomorfizmov Ljubljane je grupa reda 168. Ljubljana je točkovno-prehoden, ne pa tudi povezavno. Graf ima avtomorfizme za vsak par točk, ne pa za povezave. Zaradi tega je Ljubljana polsimetrični graf, tretji najmanjši kubični polsimetrični graf za Grayjevim grafom s 54 točkami in grafom Jofinove in Ivanova s 110 točkami.

Karakteristični polinom Ljubljane je:

$(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} \!\, .$

Zgodovina

Članek o grafu Ljubljana so prvič objavili Brouwer, Dejter in Thomassen leta 1993.

Leta 1972 je Bouwer že govoril o kubičnem grafu s 112 točkami, točkovno-prehodnem, ne pa tudi povezavno, ki ga je odkril Foster, vendar ni objavil članka o njem. Conder, Malnič, Marušič, Pisanski in Potočnik so ga odkrili neodvisno leta 2002 in ga po Conderjevem predlogu imenovali po Ljubljani. Dokazali so, da gre za edini graf s takšno značilnostjo prehodnosti, ki ga je odkril že Foster.

Upodobitve

• 

  Kromatično število Ljubljane je 2.

• 

  Kromatični indeks Ljubljane je 3.

• 

  Alternativna upodobitev Ljubljane.

• 

  Ljubljana je Levijev graf s to konfiguracijo.

Glej tudi

• Heawoodov graf

Viri

• Bouwer, I. A. (1972). "On Edge But Not Vertex Transitive Regular Graphs". J. Combin. Th. Ser. B 12: 32–40. 
• Brouwer, Andries Evert; Dejter, I. J.; Thomassen, C. (1993). "Highly Symmetric Subgraphs of Hypercubes". J. Algebraic Combinat. 2: 25–29. 
• Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Pisanski, Tomaž; Potočnik, Primož (2002). The Ljubljana Graph. http://citeseer.ist.psu.edu/conder02ljubljana.html. 
• Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Potočnik, Primož (2006). "A census of semisymmetric cubic graphs on up to 768 vertices". J. Algebraic Combin. 23 (3): 255–294. 

Zunanje povezave

• Ljubljana Graph na MathWorld (v angleščini)