Ljubljana graf
| Ljubljana-grafen | |
|---|---|
 Ljubljana-grafen som en täckande graf över Heawood-grafen
| |
| Vertices | 112 |
| Kanter | 168 |
| Radie | 7 |
| Diameter | 8 |
| Omkrets | 10 |
| Automorfismer | 168 |
| Kromatiskt nummer | 2 |
| Kromatiskt index | 3 |
| Egenskaper |
Kubisk halvsymmetrisk Hamiltonian |
| Tabell över grafer och parametrar | |
Inom det matematiska området grafteorin är Ljubljana-grafen en oriktad tvådelad graf med 112 hörn och 168 kanter .
Det är en kubikgraf med diameter 8, radie 7, kromatiskt nummer 2 och kromatiskt index 3. Dess omkrets är 10 och det finns exakt 168 cykler med längd 10 i den. Det finns också 168 cykler med längd 12.
Konstruktion
Ljubljana-grafen är Hamiltonsk och kan konstrueras från LCF-notationen : [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 är Levi-grafen för Ljubljana-konfigurationen, en fyrkantsfri konfiguration med 56 linjer och 56 punkter. I denna konfiguration innehåller varje linje exakt 3 punkter, varje punkt tillhör exakt 3 linjer och två valfria linjer skär varandra i högst en punkt.
Algebraiska egenskaper
Automorfismgruppen i Ljubljana-grafen är en grupp av ordning 168. Den verkar transitivt på grafens kanter men inte på dess hörn: det finns symmetrier som tar varje kant till någon annan kant, men tar inte varje vertex till någon annan vertex . Därför är Ljubljana-grafen en semisymmetrisk graf , den tredje minsta möjliga kubiska semisymmetriska grafen efter den grå grafen på 54 hörn och Iofinova-Ivanov-grafen på 110 hörn .
Det karakteristiska polynomet i Ljubljana-grafen är
Historia
Ljubljana-grafen publicerades första gången 1993 av Brouwer , Dejter och Thomassen som en självkompletterande subgraf till Dejter-grafen .
1972 talade Bouwer redan om en 112-hörn kant- men inte vertex-transitiv kubisk graf som hittats av RM Foster , trots det opublicerad. Conder , Malnič, Marušič , Pisanski och Potočnik återupptäckte denna graf med 112 hörn 2002 och döpte den till Ljubljana -grafen efter Sloveniens huvudstad . De bevisade att det var den unika 112-hörn kant- men inte vertex-transitiv kubisk graf och därför var det den graf som Foster hittade.
Galleri
Ljubljana-grafen är Hamiltonsk och tvådelad
Det kromatiska indexet för Ljubljana-grafen är 3.
Alternativ ritning av Ljubljana-grafen.
Ljubljana-grafen är Levi-grafen för denna konfiguration.
