Grafo mariposa
En el campo matemático de la teoría de grafos, el grafo mariposa también llamado grafo corbatín y grafo reloj de arena es un grafo plano no dirigido con 5 vértices y 6 aristas.[1][2] Está formado por dos copias del ciclo C3 con un vértice común y es isomorfo al grafo de la amistad F2.
| Grafo mariposa | ||
|---|---|---|
 | ||
| Vértices | 5 | |
| Aristas | 6 | |
| Radio | 1 | |
| Diámetro | 2 | |
| Cintura | 3 | |
| Automorfismos | 8 (D4) | |
| Número cromático | 3 | |
| Índice cromático | 4 | |
| Propiedades | ||
El grafo mariposa tiene diámetro 2 y cintura 3, radio 1, número cromático 3, índice cromático 4, es euleriano y plano. También es 1-conexo por vértices y 2-conexo por aristas
El grafo mariposa es junto a ciclo C5 y el grafo completo K5 los únicos tres tipos de grafos simples no graceful de 5 vértices.[3]
Grafo libre de corbatín
Un grafo se dice libre de corbatín si no contiene un grafo mariposa como grafo inducido. Los grafos libres de triángulos son grafos libres de corbatín, al estar formada la mariposa de dos triángulos C3.
Propiedades algebraicas
El grupo de todos los automorfismos del grafo mariposa es un grupo de orden 8 isomorfo al grupo diedral D4, el grupo de simetrías del cuadrado, incluyendo rotaciones y reflexiones
El polinomio característico del grafo mariposa es .
Referencias
- Weisstein, Eric W. «Butterfly Graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
- ISGCI: Information System on Graph Classes and their Inclusions. "List of Small Graphs"
- Weisstein, Eric W. «Graceful graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
| Control de autoridades |
|
|---|
Datos: Q3035340
Multimedia: Butterfly graph / Q3035340