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 gráfico completo menos un borde.
Gráfico de diamante | |
---|---|
Vértices | 4 |
Bordes | 5 |
Radio | 1 |
Diámetro | 2 |
Circunferencia | 3 |
Automorfismos | 4 ( Z / 2 Z × Z / 2 Z ) |
Número cromático | 3 |
Índice cromático | 3 |
Propiedades | Distancia de la unidad planar hamiltoniana |
Tabla de gráficos y parámetros |
El gráfico de diamante tiene radio 1, diámetro 2, circunferencia 3, número cromático 3 e índice cromático 3. También es un gráfico hamiltoniano elegante [3] conectado por 2 vértices y por 2 bordes .
Gráficos sin diamantes y menores prohibidos
Un gráfico está libre de diamantes si no tiene un diamante como subgrafo inducido . Los gráficos sin triángulos son gráficos sin diamantes, ya que cada diamante contiene un triángulo. Los gráficos sin diamantes están agrupados localmente: es decir, son los gráficos en los que cada vecindario es un gráfico de grupo . Alternativamente, un gráfico no tiene diamantes si y solo si cada par de grupos máximos en el gráfico comparte como máximo un vértice.
La familia de gráficos en la que cada componente conectado es un gráfico de cactus se cierra hacia abajo en operaciones menores de gráfico . Esta familia de gráficos puede caracterizarse por un solo menor prohibido . Este menor es el gráfico de diamante. [4]
Si tanto el gráfico de mariposa como el gráfico de diamante son menores de edad prohibidos, la familia de gráficos obtenidos es la familia de los pseudoforestales .
Propiedades algebraicas
El grupo de automorfismo completo del gráfico de diamante es un grupo de orden 4 isomórfico al cuatro-grupo de Klein , el producto directo del grupo cíclico Z / 2 Z consigo mismo.
El polinomio característico del gráfico de diamante es. Es el único gráfico con este polinomio característico, lo que lo convierte en un gráfico determinado por su espectro.
Ver también
Referencias
- ^ Weisstein, Eric W. "Diamante gráfico" . MathWorld .
- ^ ISGCI: Sistema de información sobre clases de gráficos y sus inclusiones " Lista de gráficos pequeños ".
- ^ Sin-Min Lee, YC Pan y Ming-Chen Tsai. "En Vértice-agraciado (p, p + l) -Gráficos". [1] Archivado el 7 de agosto de 2008 en la Wayback Machine.
- ^ El-Mallah, Ehab; Colbourn, Charles J. (1988), "La complejidad de algunos problemas de eliminación de bordes", IEEE Transactions on Circuits and Systems , 35 (3): 354–362, doi : 10.1109 / 31.1748.