Wykres Lublany
| Wykres Ljubljana | |
|---|---|
 Wykres Ljubljana jako wykres pokrywający wykres Heawood
| |
| Wierzchołki | 112 |
| Krawędzie | 168 |
| Promień | 7 |
| Średnica | 8 |
| Obwód | 10 |
| Automorfizmy | 168 |
| Liczba chromatyczna | 2 |
| Indeks chromatyczny | 3 |
| Nieruchomości |
Sześcienny półsymetryczny hamiltonian |
| Tabela wykresów i parametrów | |
W matematycznej dziedzinie teorii grafów graf Lublany jest nieskierowanym grafem dwudzielnym ze 112 wierzchołkami i 168 krawędziami .
Jest to graf sześcienny o średnicy 8, promieniu 7, liczbie chromatycznej 2 i indeksie chromatycznym 3. Jego obwód wynosi 10 i zawiera dokładnie 168 cykli o długości 10. Istnieje również 168 cykli o długości 12.
Budowa
Wykres Lublany jest hamiltonowski i można go zbudować z notacji 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 .
Wykres Ljubljana jest wykresem Leviego konfiguracji Lublany, konfiguracji pozbawionej czworokątów z 56 liniami i 56 punktami. W tej konfiguracji każda prosta zawiera dokładnie 3 punkty, każdy punkt należy do dokładnie 3 prostych, a dowolne dwie proste przecinają się co najwyżej w jednym punkcie.
Właściwości algebraiczne
Grupa automorfizmów grafu Ljubljana jest grupą rzędu 168. Działa przechodnie na krawędziach grafu, ale nie na jego wierzchołkach: istnieją symetrie prowadzące każdą krawędź do dowolnej innej krawędzi, ale nie prowadzące każdego wierzchołka do żadnego innego wierzchołka. Dlatego graf Lublany jest grafem półsymetrycznym , trzecim najmniejszym możliwym grafem półsymetrycznym sześciennym po grafie Graya na 54 wierzchołkach i grafie Iofinowej-Iwanowa na 110 wierzchołkach .
Charakterystyczny wielomian wykresu Lublany to
Historia
Wykres Ljubljana został po raz pierwszy opublikowany w 1993 roku przez Brouwera , Dejtera i Thomassena jako samouzupełniający się wykres podrzędny wykresu Dejtera .
W 1972 roku Bouwer mówił już o 112-wierzchołkowym grafie sześciennym z krawędzią, ale nie przechodnim przez wierzchołek, znalezionym przez RM Fostera , jednak niepublikowanym. Conder , Malnič, Marušič , Pisanski i Potočnik ponownie odkryli ten graf o 112 wierzchołkach w 2002 roku i nazwali go grafem Ljubljana , na cześć stolicy Słowenii . Udowodnili, że był to unikalny graf sześcienny o krawędzi 112 wierzchołków, ale nie przechodni przez wierzchołki, a zatem był to graf znaleziony przez Fostera.
Galeria
Graf Lublany jest hamiltonowski i dwudzielny
Indeks chromatyczny wykresu z Lublany wynosi 3.
Alternatywny rysunek wykresu z Lublany.
Graf Ljubljana jest wykresem Leviego w tej konfiguracji.
