Ljubljana (graf)

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Ljubljana
Ljubljana graph hamiltonian.svg
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}\!\, [1]

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.[1]

Konstrukcija[uredi | uredi kodo]

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

Ljubljana je Levijev graf s konfugracijo Ljubljana, konfiguracijo brez pravih kotov s 56 daljicami in 56 točkami.[1] 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[uredi | uredi kodo]

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.[2]

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[uredi | uredi kodo]

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

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.[4] Conder, Malnič, Marušič, Pisanski in Potočnik so ga odkrili neodvisno leta 2002 in ga po Conderjevem predlogu imenovali po Ljubljani.[1] Dokazali so, da gre za edini graf s takšno značilnostjo prehodnosti, ki ga je odkril že Foster.

Upodobitve[uredi | uredi kodo]

Glej tudi[uredi | uredi kodo]

Opombe in sklici[uredi | uredi kodo]

  1. ^ 1,0 1,1 1,2 1,3 Conder; idr. (2002).
  2. ^ Conder; idr. (2006).
  3. ^ Brouwer, Dejter, Thomassen (1993).
  4. ^ Bouwer (1972).

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]