Wykres motyla - Butterfly graph

Wykres motyla
Wierzchołki	5
Krawędzie	6
Promień	1
Średnica	2
Obwód	3
Automorfizmy	8 ( D 4 )
Liczba chromatyczna	3
Indeks chromatyczny	4
Nieruchomości	Odległość jednostkowa planarna Eulera Niezbyt elegancka
Tabela wykresów i parametrów

W matematycznej dziedzinie teorii grafów , wykres motyla (zwany również wykresem muszki i wykresem klepsydry ) jest płaskim, nie skierowanym wykresem z 5 wierzchołkami i 6 krawędziami. Można go skonstruować, łącząc 2 kopie wykresu cyklu C ₃ ze wspólnym wierzchołkiem i dlatego jest izomorficzny z grafem przyjaźni F ₂ .

Wykres motyla ma średnicę  2 i obwód  3, promień 1, liczbę chromatyczną  3, indeks chromatyczny  4 i jest wykresem Eulera i grosza (oznacza to, że jest to odległość jednostkowa i planarna ). Jest to również graf połączony z 1 wierzchołkami i grafem z 2 krawędziami .

Istnieją tylko 3 niezbyt pełne wdzięku proste grafy z pięcioma wierzchołkami. Jednym z nich jest wykres motyla. Dwa pozostałe to wykres cyklu C ₅ i pełny wykres K ₅ .

Wykresy bez muszek

Wykres jest wolny od muszki, jeśli nie ma motyla jako indukowanego podgrafu . Te wykresy trójkąt wolne są bowtie wolne wykresy, ponieważ każdy motyl zawiera trójkąt.

W k -Vertex-połączone wykresie krawędź mówi się, że k -contractible gdy skurcz krawędzi powoduje on K -connected wykresu. Ando, Kaneko, Kawarabayashi i Yoshimoto i okazało się, że każdy k -Vertex połączone muszka wolne wykres ma k -contractible krawędzi.

Własności algebraiczne

Pełna grupa automorfizmu wykresu motyla jest grupą rzędu 8 izomorficzną z grupą dwuścienną D ₄ , grupą symetrii kwadratu , obejmującą zarówno obroty, jak i odbicia.

Wielomian charakterystyczny wykresu motylkowego . ${\ Displaystyle - (x-1) (x + 1) ^ {2} (x ^ {2} -x-4)}$

Bibliografia