Fjärilsgraf

Fjärilsgraf
Vertices	5
Kanter	6
Radie	1
Diameter	2
Omkrets	3
Automorfismer	8 ( D 4 )
Kromatiskt nummer	3
Kromatiskt index	4
Egenskaper	Planar Enhet avstånd Eulerian Inte graciös
Tabell över grafer och parametrar

Inom det matematiska fältet av grafteorin är fjärilsgrafen (även kallad bowtiegrafen och timglasgrafen ) en plan , oriktad graf med 5 hörn och 6 kanter . Den kan konstrueras genom att sammanfoga 2 kopior av cykelgrafen C ₃ med en gemensam vertex och är därför isomorf till vänskapsgrafen F ₂ .

Fjärilsgrafen har diameter 2 och omkrets 3, radie 1, kromatisk nummer 3, kromatisk index 4 och är både Eulerisk och en penny-graf (detta antyder att det är enhetsavstånd och plan ). Det är också en graf med 1 vertex och en graf med 2 kant .

Det finns bara tre icke-graciösa enkla grafer med fem hörn. En av dem är fjärilsgrafen. De två andra är cykeldiagram C ₅ och hela diagrammet K ₅ .

Bowtie-fria grafer

En graf är bowtie-fri om den inte har någon fjäril som en inducerad subgraf . De triangelfria graferna är bowtie-fria grafer, eftersom varje fjäril innehåller en triangel.

I en k -vertex-kopplad graf sägs en kant vara k -kontrakterbar om sammandragningen av kanten resulterar i en k -kopplad graf. Ando, ​​Kaneko, Kawarabayashi och Yoshimoto bevisade att varje k -vertex-ansluten bowtie-fri graf har en k -kontraktibel kant.

Algebraiska egenskaper

Den fullständiga automorfismgruppen i fjärilsgrafen är en grupp av ordning 8 som är isomorf till den dihedriska gruppen D ₄ , gruppen av symmetrier i en kvadrat , inklusive både rotationer och reflektioner.

Det karakteristiska polynomet för fjärilsgrafen är $-(x-1)(x+1)^{2}(x^{ 2}-x-4)$ .