Shrikhande wykres - Shrikhande graph
Shrikhande wykres | |
---|---|
Wykres Shrikhande
| |
Nazwany po | SS Shrikhande |
wierzchołki | 16 |
Obrzeża | 48 |
Promień | 2 |
Średnica | 2 |
Obwód | 3 |
automorfizmy | 192 |
liczba chromatyczna | 4 |
indeks chromatyczny | 6 |
grubość książki | 4 |
Numer kolejka | 3 |
Nieruchomości |
Silnie regularny Hamiltona Symetryczna Eulera Integral |
Tabela wykresów i parametrów |
W matematycznej dziedzinie teorii grafów The wykres Shrikhande jest nazwany wykres odkryta przez SS Shrikhande w roku 1959. Jest to zdecydowanie graf regularny z 16 wierzchołków i 48 krawędzi , przy czym każdy wierzchołek mający stopień 6. Każda para węzłów ma dokładnie dwa inne sąsiedzi wspólnego, czy para węzłów jest podłączony czy nie.
Budowa
Wykres Shrikhande może być wykonany w postaci wykresu Cayley . Zbiór wierzchołków jest . Dwa wierzchołki sąsiadują wtedy i tylko wtedy, gdy różnica jest .
Nieruchomości
Na wykresie Shrikhande, dowolne dwa wierzchołki I i J posiadają dwa różne sąsiadów często (z wyjątkiem dwóch wierzchołków I i J ), które to prawdą nawet , że przylega do J . Innymi słowy, jest silnie regularny i jego parametry są następujące: {16,6,2,2}, tzn . Ta równość oznacza, że wykres jest związany z symetrycznym BIBD . W Shrikhande akcji wykres te parametry z dokładnie jednym drugim wykresie, 4 x 4- wykres gawroni , czyli wykres linii L ( K 4,4 ) o całkowitym dwuczęściowego wykresie K 4,4 . Ten ostatni wykres jest tylko wykres linii L ( K n, n ), w których silne parametry regularność nie wskazują jednoznacznie, że wykres lecz wspólnie z innym, a mianowicie wykres krzywej Shrikhande (co nie jest Graph gawroni).
Wykres Shrikhande jest lokalnie sześciokątny ; Oznacza to, że sąsiedzi każdego wierzchołka tworzą cykl sześciu wierzchołkach. Tak jak w przypadku jakiegokolwiek cyklicznego lokalnie wykres wykres Shrikhande jest 1 szkieletu z Whitney triangulacji jakiejś powierzchni; W przypadku wykresu Shrikhande, powierzchnia ta jest torusa , w którym każdy wierzchołek jest otoczony przez sześć trójkątów. Zatem wykres Shrikhande jest toroidalny wykres . Osadzanie tworzy regularną mapę w torusa, z 32 trójkątnych twarzach. Szkielet tej podwójnej mapy (osadzoną w torusa) stanowi wykres Dyck , sześcienny symetryczny wykres.
Wykres Shrikhande nie jest wykres na odległość przechodnia . Jest to najmniejsza odległość-graf regularny , że nie jest na odległość przechodnia.
Grupa automorfizmem wykresu Shrikhande jest rzędu 192. działa przechodni na wierzchołkach, na krawędziach i łuków wykresu. W związku z tym, na wykresie Shrikhande jest symetryczny wykres .
Wielomian charakterystyczny wykresu Shrikhande jest: . W związku z tym, na wykresie Shrikhande jest integralną wykres : jego widmo składa się w całości z liczb całkowitych.
Ma ona grubość książki 4 i kolejki numer 3.
Galeria
Wykres Shrikhande jest toroidalny wykres .
Liczba chromatyczna wykresu Shrikhande 4.
Chromatycznej wskaźnik wykresu Shrikhande to 6.
Wykres Shrikhande jest Hamiltona .
Uwagi
Referencje
- Holton, Da; Sheehan, J. (1993), Petersen Graph , Cambridge University Press , s. 270, ISBN 0-521-43594-3,
Linki zewnętrzne
- Shrikhande Graph , Peter Cameron , sierpień 2010.