Motýl (teorie grafů)

V teorii grafů je motýlí graf (také známý jako motýlek nebo přesýpací hodiny ) rovinný neorientovaný graf s 5 vrcholy a 6 hranami [1] [2] . Graf lze sestrojit spojením dvou kopií cyklů C 3 v jednom společném vrcholu, a proto je graf izomorfní ke grafu přátelství F 2 .

Motýl má průměr  2 a obvod  3, poloměr 1, chromatické číslo  3, chromatický index  4 a je jak Euler , tak graf jednotkové vzdálenosti . Graf je spojen 1 vrcholem a 2 hraněmi .

Existují pouze 3 jednoduché grafy s pěti vrcholy , které nemají elegantní označení . Jedním z nich je motýl. Další dva jsou cyklus C 5 a úplný graf K 5 [3] .

Grafy bez motýlů

Graf je bez motýlů, pokud nemá motýla jako vygenerovaný podgraf . Grafy bez trojúhelníků jsou grafy bez motýlů, protože motýlí graf obsahuje trojúhelníky.

Ve vrcholovém k - spojeném grafu se o hraně říká , že je k -stahující se, pokud kontrakce hrany vede ke k - souvislému grafu. Ando, ​​​​Kaneko, Kawarabayashi a Yoshimoto dokázali, že každý k -vertex -spojený bez motýlkový graf má k -zatažitelný okraj [4] .

Algebraické vlastnosti

Plná skupina automorfismu motýlího grafu je skupina řádu 8 izomorfní k D 4 , grupa symetrie čtverce , včetně rotace a odrazů.

Charakteristickým polynomem matice motýlího grafu je .

Poznámky

1. ↑ Weisstein, Eric W. Butterfly Graph  na webu Wolfram MathWorld .
2. ↑ ISGCI: Informační systém o třídách grafů a jejich zahrnutí. " Seznam malých grafů archivovaný 22. července 2012 na Wayback Machine ".
3. ↑ Weisstein, Eric W. Graceful graph  na webu Wolfram MathWorld .
4. ↑ Ando, ​​​​2007 , str. 10–20.

Literatura

• Kiyoshi Ando. Diskrétní geometrie, kombinatorika a teorie grafů. - Springer, Berlín, 2007. - T. 4381. - S. 10–20. - (Poznámky z přednášky v počítačové vědě). - doi : 10.1007/978-3-540-70666-3_2 .