Pillangó (gráfelmélet)
| Gróf "pillangó" | |
|---|---|
| Csúcsok | 5 |
| borda | 6 |
| Sugár | egy |
| Átmérő | 2 |
| Heveder | 3 |
| Automorfizmusok | 8 ( D4 ) |
| Kromatikus szám | 3 |
| Kromatikus index | négy |
| Tulajdonságok |
az eulerek síkbeli egységtávolsági grafikonja nem rendelkezik kecses feliratozással |
| Médiafájlok a Wikimedia Commons oldalon | |
A gráfelméletben a pillangógráf (más néven csokornyakkendő vagy homokóra ) egy síkbeli irányítatlan gráf , amelynek 5 csúcsa és 6 éle van [1] [2] . A gráf összeállítható úgy, hogy a C 3 ciklusok két másolatát egy közös csúcsban összekapcsoljuk, ezért a gráf izomorf az F 2 barátsági gráfhoz .
A pillangó átmérője 2, kerülete 3, sugara 1, kromatikus száma 3, kromatikus indexe 4, és egyszerre Euler és egységnyi távolsággráf . A gráf 1 csúcshoz és 2 élhez kapcsolódik .
Csak 3 egyszerű, öt csúcsú gráf létezik , amelyeknek nincs kecses címkézése . Egyikük egy pillangó. A másik kettő a C 5 ciklus és a K 5 teljes gráf [3] .
Pillangómentes grafikonok
Egy gráf pillangómentes , ha nem tartalmaz pillangót generált részgráfként . A háromszög nélküli grafikonok pillangómentes grafikonok, mivel a pillangógráf háromszögeket tartalmaz.
Egy k csúcsú gráfban egy élt k -összehúzónak mondunk, ha az él összehúzódása egy k -kapcsolt gráfhoz vezet. Ando, Kaneko, Kawarabayashi és Yoshimoto bebizonyították, hogy minden k -csúcshoz kapcsolódó pillangómentes gráfnak van k - visszahúzható éle [4] .
Algebrai tulajdonságok
A pillangógráf teljes automorfizmuscsoportja egy 8-as rendű izomorf csoport D 4 -el, egy négyzet szimmetriacsoportja , beleértve a forgatást és a visszaverődéseket.
A pillangógráf mátrix karakterisztikus polinomja a .
Jegyzetek
- ↑ Weisstein, Eric W. Butterfly Graph a Wolfram MathWorld webhelyén .
- ↑ ISGCI: Információs rendszer a grafikonosztályokról és azok befogadásairól. " A kis grafikonok listája archiválva 2012. július 22-én a Wayback Machine -nél ".
- ↑ Weisstein, Eric W. Graceful grafikon a Wolfram MathWorld webhelyen .
- ↑ Ando, 2007 , p. 10–20.
Irodalom
- Kiyoshi Ando. Diszkrét geometria, kombinatorika és gráfelmélet. - Springer, Berlin, 2007. - T. 4381. - S. 10–20. - (Előadási jegyzetek a Comput. Sci.-ben). - doi : 10.1007/978-3-540-70666-3_2 .