Fjäril (grafteori)
| 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] .
Fjärilsfria grafer
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] .
Algebraiska egenskaper
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 .
Anteckningar
- ↑ Weisstein, Eric W. Butterfly Graph på Wolfram MathWorld- webbplatsen .
- ↑ ISGCI: Informationssystem om grafklasser och deras inneslutningar. " Lista över små grafer arkiverade 22 juli 2012 på Wayback Machine ".
- ↑ Weisstein, Eric W. Graceful graf på Wolfram MathWorld- webbplatsen .
- ↑ Ando, 2007 , sid. 10–20.
Litteratur
- Kiyoshi Ando. Diskret geometri, kombinatorik och grafteori. - Springer, Berlin, 2007. - T. 4381. - S. 10–20. - (Lecture Notes in Comput. Sci.). - doi : 10.1007/978-3-540-70666-3_2 .