En el campo matemático de la teoría de grafos , el grafo de mariposa (también llamado grafo de moño y grafo de reloj de arena ) es un grafo plano , no dirigido, con 5 vértices y 6 aristas. [1] [2] Se puede construir uniendo 2 copias del grafo de ciclo C 3 con un vértice común y, por lo tanto, es isomorfo al grafo de amistad F 2 .
El grafo de la mariposa tiene un diámetro de 2 y una circunferencia de 3, un radio de 1, un número cromático de 3, un índice cromático de 4 y es tanto euleriano como de penique (esto implica que es una unidad de distancia y plano ). También es un grafo conexo por 1 vértice y un grafo conexo por 2 aristas .
Sólo hay tres grafos simples no elegantes con cinco vértices. Uno de ellos es el grafo mariposa. Los otros dos son el grafo cíclico C 5 y el grafo completo K 5 . [3]
Un grafo no tiene moños si no tiene mariposas como subgrafo inducido . Los grafos sin triángulos son grafos sin moños, ya que cada mariposa contiene un triángulo.
En un grafo conexo por k vértices , se dice que una arista es k -contráctil si la contracción de la arista da como resultado un grafo conexo por k vértices. Ando, Kaneko, Kawarabayashi y Yoshimoto demostraron que todo grafo sin moño conexo por k vértices tiene una arista k -contráctil. [4]
El grupo de automorfismo completo del grafo de la mariposa es un grupo de orden 8 isomorfo al grupo diedro D 4 , el grupo de simetrías de un cuadrado , que incluye tanto rotaciones como reflexiones.
El polinomio característico del gráfico de la mariposa es .
