Wykres Folkmana - Folkman graph
| Wykres Folkman | |
|---|---|
 Wykres Folkman
| |
| Nazwany po | Jon Folkman |
| Wierzchołki | 20 |
| Krawędzie | 40 |
| Promień | 3 |
| Średnica | 4 |
| Obwód | 4 |
| Automorfizmy | 3840 |
| Liczba chromatyczna | 2 |
| Indeks chromatyczny | 4 |
| Grubość książki | 3 |
| Numer kolejki | 2 |
| Nieruchomości |
Hamiltonian Regularny Dwudzielny Semi-symetryczny Eulerowski Perfect |
| Tabela wykresów i parametrów | |
W matematycznej dziedzinie teorii grafów , w Folkman wykresie , nazwany Jon Folkman , jest dwudzielny 4- regularne wykres z 20 wierzchołków i 40 krawędzi.
Graf Folkmana jest hamiltonianem i ma liczbę chromatyczną 2, indeks chromatyczny 4, promień 3, średnicę 4 i obwód 4. Jest to również graf idealny z 4 wierzchołkami i 4 krawędziami . Ma grubość książki 3 i kolejkę numer 2.
Własności algebraiczne
Grupa automorfizmu grafu Folkmana działa przechodnie na jego krawędziach, ale nie na jego wierzchołkach. Jest to najmniejszy graf nieskierowany, który jest przechodni krawędziowo i regularny, ale nie jest przechodni wierzchołków . Takie grafy nazywane są grafami półsymetrycznymi i zostały po raz pierwszy zbadane przez Folkmana w 1967 roku, który odkrył graf na 20 wierzchołkach, który teraz jest nazwany jego imieniem.
Jako graf półsymetryczny, graf Folkmana jest dwudzielny , a jego grupa automorfizmu działa przechodnie na każdym z dwóch zestawów wierzchołków dwudzielności. Na poniższym diagramie wskazującym liczbę chromatyczną wykresu, zielone wierzchołki nie mogą być mapowane na czerwone przez żaden automorfizm, ale każdy czerwony wierzchołek może być mapowany na dowolny inny czerwony wierzchołek i dowolny zielony wierzchołek może być mapowany na dowolny inny zielony wierzchołek .
Wielomian charakterystyczny z Folkman grafu .
Galeria
Chromatycznej wskaźnik z Folkman wykresie 4.
Liczba chromatyczna wykresu Folkman wynosi 2.
Wykres Folkmana jest Hamiltonianem .
