Ljubljanski graf
Ljubljanski graf 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  ciklov dolžine 10. Graf ima tudi 168 ciklov dolžine 12.

Konstrukcija 

Ljubljanski graf je Hamiltonov graf in se ga lahko skonstruira 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.

Ljubljanski graf je Levijev graf s konfugracijo Ljubljanskega grafa, 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 Ljubljanskega grafa je grupa reda 168. Ljubljanski graf je točkovnoprehoden, ne pa tudi povezavno. Graf ima avtomorfizme za vsak par točk, ne pa za povezave. Zaradi tega je Ljubljanski graf 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 Ljubljanskega grafa je:

Zgodovina 

Članek o Ljubljanskem grafu so prvič objavili Brouwer, Dejter in Thomassen leta 1993 kot sebikomplementarni podgraf Dejterovega grafa.

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

Glej tudi 

 Heawoodov graf

Sklici

Viri

Zunanje povezave 

 
 Umetniška upodobitev Ljubljanskega grafa 

Posamezni grafi
Regularni grafi
1993 v znanosti
Ljubljanski graf je v teoriji grafov neusmerjeni dvodelni graf stočkami inpovezavami . Je kubični graf s premerom polmerom kromatičnim številomin kromatičnim indeksom Njegov notranji obseg je v njem pa je točno ciklov dolžine Graf ima tudiciklov dolžine Konstrukcija Ljubljanski graf je Hamiltonov graf in se ga lahko skonstruira iz zapisa LCF \ : [ 47 , 2. Ljubljanski graf je Levijev graf s konfugracijo Ljubljanskega grafa , konfiguracijo brez pravih kotov sdaljicami intočkami . V takšni konfiguraciji vsaka daljica vsebuje točnotočke , vsaka točka pripada točnodaljicam in poljubni par daljic se seka v samo eni točki . Algebrske značilnosti Grupa avtomorfizmov Ljubljanskega grafa je grupa reda Ljubljanski graf je točkovnoprehoden , ne pa tudi povezavno . Graf ima avtomorfizme za vsak par točk , ne pa za povezave . Zaradi tega je Ljubljanski graf polsimetrični graf , tretji najmanjši kubični polsimetrični graf za Grayjevim grafom stočkami in grafom Jofinove in Ivanova stočkami . Karakteristični polinom Ljubljanskega grafa je : Zgodovina Članek o Ljubljanskem grafu so prvič objavili Brouwer , Dejter in Thomassen letakot sebikomplementarni podgraf Dejterovega grafa . Letaje Bouwer že govoril o kubičnem grafu stoč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 letain 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 Glej tudi Heawoodov graf Sklici Viri Zunanje povezave Umetniška upodobitev Ljubljanskega grafa Posamezni grafi Regularni grafi 1993 v znanosti