Pillangógráf
| Pillangógráf | |
 | |
| Csúcsok száma | 5 |
| Élek száma | 6 |
| Sugár | 1 |
| Átmérő | 2 |
| Derékbőség | 3 |
| Kromatikus szám | 3 |
| Élkromatikus szám | 4 |
| Automorfizmusok | 8 (D4) |
| Egyéb | Síkgráf Egységtávolsággráf Euler-körű gráf Nem graceful |
A matematika, azon belül a gráfelmélet területén a pillangógráf (butterfly graph), csokornyakkendő-gráf (bowtie graph) vagy homokóra-gráf (hourglass graph) egy 5 csúccsal és 6 éllel rendelkező irányítatlan síkbarajzolható gráf.[1][2] Megkonstrukálható a C3 körgráf két kópiájának egy közös csúcsban való összefűzésével, ezért izomorf az F2 barátsággráffal.
A pillangógráf átmérője 2, girthparamétere 3, sugara 1, kromatikus száma 3, élkromatikus száma 4; Euler-körű gráf és egységtávolsággráf. 1-szeresen csúcsösszefüggő és 2-szeresen élösszefüggő.
Az öt csúcsú gráfok közül csak 3 nem graceful címkézhető: ezek egyike a pillangógráf, a másik kettő a C5 körgráf és a K5 teljes gráf.[3]
Pillangómentes gráfok
[szerkesztés]Egy gráf pillangómentes, ha nem tartalmazza a pillangógráfot feszített részgráfjaként. A háromszögmentes gráfok mind pillangómentesek, hiszen a pillangó tartalmaz háromszöget.
Egy k-szorosan csúcsösszefüggő gráfban egy él k-összehúzható, ha az él összehúzása egy k-szorosan csúcsösszefüggő gráfot eredményez. Ando, Kaneko, Kawarabayashi és Yoshimoto igazolták, hogy minden k-csúcsösszefüggő pillangómentes gráf rendelkezik k-összehúzható éllel.[4]
Algebrai tulajdonságok
[szerkesztés]A pillangógráf automorfizmus-csoportjának rendje 8, izomorf a D4 diédercsoporttal, a négyzet forgatásokat és tükrözéseket is figyelembe vevő szimmetriacsoportjával.
A pillangógráf karakterisztikus polinomja .
Fordítás
[szerkesztés]- Ez a szócikk részben vagy egészben a Butterfly graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek
[szerkesztés]- ↑ Weisstein, Eric W.: Butterfly Graph (angol nyelven). Wolfram MathWorld
- ↑ ISGCI: Information System on Graph Classes and their Inclusions. "List of Small Graphs".
- ↑ Weisstein, Eric W.: Graceful graph (angol nyelven). Wolfram MathWorld
- ↑ Ando, Kiyoshi (2007), "Contractible edges in a k-connected graph", Discrete geometry, combinatorics and graph theory, vol. 4381, Lecture Notes in Comput. Sci., Springer, Berlin, pp. 10–20, DOI 10.1007/978-3-540-70666-3_2.