Motýl (teorie grafů)

hrabě "motýl"
Vrcholy 5
žebra 6
Poloměr jeden
Průměr 2
obvod 3
Automorfismy 8 ( D4 )
Chromatické číslo 3
Chromatický index čtyři
Vlastnosti graf vzdálenosti rovinných
jednotek
eulerů
nemá elegantní značení
 Mediální soubory na Wikimedia Commons

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