Räkna "Fjäril" | |
---|---|
Toppar | 5 |
revben | 6 |
Radie | ett |
Diameter | 2 |
Omkrets | 3 |
Automorfismer | 8 ( D4 ) |
Kromatiskt nummer | 3 |
Kromatiskt index | fyra |
Egenskaper |
den plana enhetsavståndsgrafen för eulers har inte graciös märkning |
Mediafiler på Wikimedia Commons |
I grafteorin är en fjärilsgraf (även känd som fluga eller timglas ) en plan oriktad graf med 5 hörn och 6 kanter [1] [2] . Grafen kan konstrueras genom att sammanfoga två kopior av cyklerna C 3 vid en gemensam vertex, och därför är grafen isomorf till vänskapsgrafen F 2 .
Fjärilen har en diameter på 2 och en omkrets på 3, en radie på 1, ett kromatiskt tal på 3, ett kromatiskt index på 4, och är både Euler och en enhetsdistansgraf . Grafen är 1-vertex-ansluten och 2-kant-ansluten .
Det finns bara 3 enkla grafer med fem hörn som inte har en elegant märkning . En av dem är en fjäril. De andra två är cykeln C 5 och den fullständiga grafen K 5 [3] .
En graf är fjärilsfri om den inte har en fjäril som genererad subgraf . Triangelfria grafer är fjärilsfria grafer eftersom en fjärilsgraf innehåller trianglar.
I en vertex k -kopplad graf sägs en kant vara k -sammandragande om kantens sammandragning leder till en k -kopplad graf. Ando, Kaneko, Kawarabayashi och Yoshimoto bevisade att varje k -vertex -ansluten fjärilsfri graf har en k -indragbar kant [4] .
Den fullständiga automorfismgruppen i en fjärilsgraf är en grupp av ordningen 8 isomorf till D 4 , symmetrigruppen för en kvadrat , inklusive rotation och reflektioner.
Det karakteristiska polynomet för fjärilsgrafmatrisen är .