En el campo matemático de la teoría de grafos , el gráfico de mariposa (también llamado gráfico de pajarita y gráfico de reloj de arena ) es un gráfico plano no dirigido con 5 vértices y 6 aristas. [1] [2] Se puede construir uniendo 2 copias del gráfico de ciclo C 3 con un vértice común y, por lo tanto, es isomorfo al gráfico de amistad F 2 .
Gráfico de mariposa | |
---|---|
Vértices | 5 |
Bordes | 6 |
Radio | 1 |
Diámetro | 2 |
Circunferencia | 3 |
Automorfismos | 8 ( D 4 ) |
Número cromático | 3 |
Índice cromático | 4 |
Propiedades | Planar unidad de distancia euleriano No grácil |
Tabla de gráficos y parámetros |
El gráfico de mariposa tiene diámetro 2 y circunferencia 3, radio 1, número cromático 3, índice cromático 4 y es tanto euleriano como de centavo (esto implica que es unidad de distancia y plano ). También es un gráfico conectado por 1 vértice y un gráfico conectado por 2 aristas .
Solo hay 3 gráficos simples sin gracia con cinco vértices. Uno de ellos es el gráfico de mariposas. Los otros dos son el gráfico de ciclo C 5 y el gráfico completo K 5 . [3]
Gráficos sin pajarita
Un gráfico no tiene pajarita si no tiene una mariposa como subgrafo inducido . Los gráficos sin triángulos son gráficos sin pajaritas, ya que cada mariposa contiene un triángulo.
En un gráfico conectado con k - vértices, se dice que una arista es k -contraíble si la contracción de la arista da como resultado una grafica con k -conectadas. Ando, Kaneko, Kawarabayashi y Yoshimoto demostraron que cada gráfico libre de pajarita conectado con k -vértices tiene un borde k -contractible. [4]
Propiedades algebraicas
El grupo de automorfismo completo del gráfico de 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 mariposa es.
Referencias
- ^ Weisstein, Eric W. "Gráfico de mariposa" . MathWorld .
- ^ ISGCI: Sistema de información sobre clases de gráficos y sus inclusiones. " Lista de gráficos pequeños ".
- ^ Weisstein, Eric W. "Gráfica elegante" . MathWorld .
- ^ Ando, Kiyoshi (2007), "Aristas contráctiles en un grafo conectado k ", Geometría discreta, combinatoria y teoría de grafos , Lecture Notes in Comput. Sci., 4381 , Springer, Berlín, págs. 10-20, doi : 10.1007 / 978-3-540-70666-3_2 , MR 2364744.