Wykres Grötzscha

Wykres Grötzscha
Reprezentacja wykresu Grötzscha.

Liczba wierzchołków	11
Liczba krawędzi	20
Dystrybucja stopni	3 (5 wierzchołków) 4 (5 wierzchołków) 5 (1 wierzchołek)
Promień	2
Średnica	2
Siatka	4
Automorfizmy	10 ( D 5 )
Liczba chromatyczna	4
Indeks chromatyczny	5
Nieruchomości	Hamiltonian

Wykres Grötzsch jest w teorii wykres , wykres z wierzchołków 11 i 20 krawędzi. Jest to najmniejszy wykres bez trójkąta o chromatycznej liczbie 4.

Jej nazwa pochodzi od Herberta Grötzscha, który odkrył ją w 1958 roku.

Budowa

Graf Grötscha można postrzegać jako graf Mycielskiego zbudowany z grafu cyklicznego z pięcioma wierzchołkami:

dla każdego wierzchołka wykresu cyklu tworzymy nowy wierzchołek połączony z dwoma sąsiadami ; $v_ {i}$ $u_i$ $v_ {i}$
następnie tworzymy nowy wierzchołek połączony ze wszystkimi . $w$ $u_i$

Nieruchomości

Właściwości ogólne

Średnica wykresu Grötzsch maksymalna mimośrodowość wierzchołków, wynosi 2, jego promień minimalny mimośród wierzchołków, wynosi 2, a jego oczka , długość najkrótszej cyklu , to 4. Ma on 3- wierzchołka -graf połączony i graf połączony z 3 krawędziami , czyli jest połączony i aby go rozłączyć, musi być pozbawiony co najmniej 3 wierzchołków lub 3 krawędzi.

Graf Grötzscha jest hamiltonowskim (ilustracja) .

Kolorowanie

Liczba chromatyczna wykresu Grötzscha wynosi 4. To znaczy, że można go pokolorować 4 kolorami, tak że dwa wierzchołki połączone krawędzią mają zawsze różne kolory. Ta liczba jest minimalna.

Chromatycznej wskaźnik wykresu Grötzsch to 5. Istnieje zatem 5 barwienia krawędzi grafu, tak że dwie krawędzie incydent ten sam wierzchołek zawsze są w różnych kolorach. Ta liczba jest minimalna.

Można policzyć wyraźne zabarwienia wykresu Grötzscha. Daje to funkcję zależną od liczby dozwolonych kolorów. Jest to funkcja wielomianowa, a związany z nią wielomian nazywany jest wielomianem chromatycznym . Ten wielomianem stopnia 11 przyznaje korzenie wszystkich dodatnich liczb całkowitych lub zero ściśle mniej niż 4. Jest ona równa: . ${\ Displaystyle (x-3) (x-2) (x-1) x (x ^ {7} -14x ^ {6} + 95x ^ {5} -400x ^ {4} + 1115x ^ {3} - 2033x ^ {2} + 2217x-1100)}$

Właściwości algebraiczne

Grupa automorfizmów grafu Grötzscha to grupa rzędu 10 izomorficzna z grupą dwuścienną D 5 , grupą izometrii płaszczyzny zachowującej regularny pięciokąt . Ta grupa składa się z 5 elementów odpowiadających obrotom i 5 innych elementów odpowiadających odbiciom .

Wielomian charakterystyczny z matrycy przylegania z Grötzsch wykresie oznacza: . ${\ Displaystyle - (x-1) ^ {5} (x ^ {2} -x-10) (x ^ {2} + 3x + 1) ^ {2}}$

Zobacz też

Linki wewnętrzne

Teoria grafów

Linki zewnętrzne

(en) Eric W. Weisstein , Grötzsch Graph ( MathWorld )

Bibliografia

(w) Vašek Chvátal , "The minimalności wykresu Mycielski" w wykresach i Kombinatoryka (Proc. Capital Conf., George Washington Univ., Washington, DC, 1973) , vol. 406 Springer-Verlag1974, strony 243–246.
(w) Alexander Soifer, The Mathematical Coloring Book , Springer, 2009, ( ISBN 978-0-387-74640-1 ) , strona 86.