En el campo matemático de la teoría de grafos , el grafo de diamante es un grafo plano , no dirigido, con 4 vértices y 5 aristas. [1] [2] Consiste en un grafo completo menos una arista.
El grafo de diamante tiene radio 1, diámetro 2, circunferencia 3, número cromático 3 e índice cromático 3. También es un grafo hamiltoniano elegante , conectado por 2 vértices y conectado por 2 aristas [ 3] .
Un grafo no tiene diamantes si no tiene ningún diamante como subgrafo inducido . Los grafos sin triángulos son grafos sin diamantes, ya que cada diamante contiene un triángulo. Los grafos sin diamantes están agrupados localmente: es decir, son los grafos en los que cada vecindario es un grafo de agrupamiento . Alternativamente, un grafo no tiene diamantes si y solo si cada par de camarillas máximas en el grafo comparte como máximo un vértice.
La familia de grafos en la que cada componente conectado es un grafo de cactus está cerrada hacia abajo bajo las operaciones de grafos menores . Esta familia de grafos puede caracterizarse por un único grafo menor prohibido . Este grafo menor es el grafo de diamante. [4]
Si tanto el gráfico de mariposa como el gráfico de diamante son menores prohibidos, la familia de gráficos obtenida es la familia de pseudobosques .
El grupo de automorfismo completo del grafo de diamante es un grupo de orden 4 isomorfo al cuatro-grupo de Klein , el producto directo del grupo cíclico consigo mismo.
El polinomio característico del grafo del diamante es . Es el único grafo con este polinomio característico, lo que lo convierte en un grafo determinado por su espectro.
