Wykres zero-symetryczny - Zero-symmetric graph
W matematycznej dziedzinie teorii wykres , A zero symetryczny wykres jest połączony wykres , w którym każdy wierzchołek ma dokładnie trzy krawędzie ze zdarzeń, a dla każdego z dwóch wierzchołków, jest unikalny symetrii przy jednym wierzchołkiem do drugiej. Taki graf jest grafem przechodnim wierzchołkowym, ale nie może być grafem przechodnim krawędziowym : liczba symetrii jest równa liczbie wierzchołków, zbyt mało, aby przenieść każdą krawędź do każdej innej krawędzi.
Nazwa tej klasy wykresów została ukuta przez RM Fostera w liście do HSM Coxeter z 1966 roku . W kontekście teorii grup zero-symetryczne grafy są również nazywane graficznymi regularnymi reprezentacjami ich grup symetrii.
Przykłady
Najmniejszy graf zero-symetryczny to graf nieplanarny z 18 wierzchołkami. Jego notacja LCF to [5,−5] 9 .
Między płaskimi wykresów , że ścięta cuboctahedral i ściętego icosidodecahedral wykresy również zero symetryczne.
Wszystkie te przykłady są wykresami dwudzielnymi . Istnieją jednak większe przykłady grafów o zerowej symetrii, które nie są dwudzielne.
Te przykłady mają również trzy różne klasy symetrii (orbity) krawędzi. Istnieją jednak grafy o symetrii zerowej z tylko dwoma orbitami krawędzi. Najmniejszy taki graf ma 20 wierzchołków z notacją LCF [6,6, -6, -6] 5 .
Nieruchomości
Każdy skończony zero-symetryczny graf jest grafem Cayleya , właściwość, która nie zawsze obowiązuje dla grafów przechodnich wierzchołków sześciennych bardziej ogólnie i która pomaga w rozwiązywaniu kombinatorycznych zadań wyliczania dotyczących grafów zerowo-symetrycznych. Istnieje 97687 zero-symetrycznych wykresów na maksymalnie 1280 wierzchołkach. Wykresy te tworzą 89% sześciennych wykresów Cayleya i 88% wszystkich połączonych sześciennych grafów przechodnich wierzchołków na tej samej liczbie wierzchołków.
Czy każdy skończony graf symetryczny zero zawiera cykl Hamiltona ?
Wszystkie znane grafy zero-symetryczne o skończeniu spójnych zawierają cykl hamiltonowski , ale nie wiadomo, czy każdy graf o skończenie spójnych zero-symetrycznych jest koniecznie hamiltonianem. Jest to szczególny przypadek hipotezy Lovásza, że (z pięcioma znanymi wyjątkami, z których żaden nie jest zero-symetryczny) każdy skończenie połączony graf przechodni wierzchołkowy i każdy skończony graf Cayleya jest hamiltonianem.
Zobacz też
- Wykres półsymetryczny , grafy, które mają symetrie między każdymi dwiema krawędziami, ale nie między każdymi dwoma wierzchołkami (odwrócenie ról krawędzi i wierzchołków w definicji grafów zerosymetrycznych)