Greve af Ljubljana

Greve af Ljubljana

Greve af Ljubljana som dækkende greve af grev Heawood
Toppe 112
ribben 168
Radius 7
Diameter otte
Omkreds ti
Automorfismer 168
Kromatisk tal 2
Kromatisk indeks 3
Ejendomme Kubisk
Hamilton
-semisymmetrisk
 Mediefiler på Wikimedia Commons

Ljubljana-grafen er en urettet todelt graf med 112 hjørner og 168 kanter [1] .

Grafen er en kubisk graf med diameter 8, radius 7, kromatisk nummer 2 og kromatisk indeks 3. Dens omkreds er 10, og den har præcis 168 cyklusser af længden 10. Der er også 168 cyklusser af længden 12 [2] .

Konstruktion

Ljubljana-grafen er Hamiltonsk og kan konstrueres ud fra en LCF-kode  : [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 - grafen er Lévy-grafen for Ljubljana-konfigurationen, en firkantfri konfiguration med 56 linjer og 56 punkter [2] . I denne konfiguration indeholder hver linje præcis 3 punkter, hvert punkt tilhører nøjagtigt 3 linjer, og to linjer skærer hinanden i højst ét ​​punkt.

Algebraiske egenskaber

Automorfigruppen i Ljubljana-grafen er en gruppe af orden 168. Den virker transitivt på kanter, men ikke på hjørner - der er symmetrier , der tager en hvilken som helst kant til en hvilken som helst anden kant, men der er ingen symmetri, der fører ethvert toppunkt til ethvert andet toppunkt. . Derfor er Ljubljana-grafen en semisymmetrisk graf , den tredje kubiske semisymmetriske graf efter den grå graf med 54 hjørner og Ivanov-Iofinova-grafen med 110 spidser [3] .

Det karakteristiske polynomium i Ljubljana-grafen er

Historie

Ljubljana-greven blev første gang udgivet i 1993 af Brouwer, Dejter og Thomassen [4] som en selvkomplementær subgraf af Dejter-greven [5] .

I 1972 talte Brouwer allerede om en 112-vertex kanttransitiv, men ikke toppunkttransitiv, kubisk graf fundet af Foster , men ikke offentliggjort [6] . Conder, Malnic, Marušić og Potocnik genopdagede denne graf med 112 hjørner i 2002 og kaldte den greven af ​​Ljubljana efter hovedstaden i Slovenien [2] . De beviste, at grafen var den eneste 112-vertex kant-transitive, men ikke vertex-transitive, kubiske graf, og derfor er den samme graf, som Foster fandt.

Galleri

Noter

  1. ↑ Weisstein, Eric W. Ljubljana Graf  på Wolfram MathWorld- webstedet .
  2. ↑ 1 2 3 Conder, Malnič, Marušič, Pisanski, Potočnik, 2002 .
  3. ↑ Conder, Malnič, Marušič, Potočnik, 2006 , s. 255-294.
  4. ↑ Brouwer, Dejter, Thomassen, 1993 , s. 25-29.
  5. ↑ Klin, Lauri, Ziv-Av, 2012 , s. 1175-1191.
  6. ↑ Bouwer, 1972 , s. 32-40.

Litteratur