Pillangógráf

Sablon:Gráf infobox 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. Megkonstrukálható a C₃ körgráf két kópiájának egy közös csúcsban való összefűzésével, ezért izomorf az F₂ 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 C₅ körgráf és a K₅ teljes gráf.

Pillangómentes gráfok

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.

Algebrai tulajdonságok

A pillangógráf automorfizmus-csoportjának rendje 8, izomorf a D₄ diédercsoporttal, a négyzet forgatásokat és tükrözéseket is figyelembe vevő szimmetriacsoportjával.

A pillangógráf karakterisztikus polinomja $-(x-1)(x+1{)}^2(x^2-x-4)$.

Fordítás

• Sablon:Fordítás