Diamante (teoría de grafos)
| Diamante | |
|---|---|
| picos | cuatro |
| costillas | 5 |
| Radio | una |
| Diámetro | 2 |
| Circunferencia | 3 |
| automorfismos | 4 ( Z / 2 Z × Z / 2 Z ) |
| número cromático | 3 |
| índice cromático | 3 |
| Propiedades |
Gráfico de distancia unitaria hamiltoniana planar |
| Archivos multimedia en Wikimedia Commons | |
Diamond es un gráfico plano no dirigido con 4 vértices y 5 aristas [1] [2] . Un gráfico es un gráfico completo sin un borde.
El radio del diamante es 1, el diámetro es 2, la circunferencia es 3, el índice cromático y el número cromático son 3. El gráfico también está conectado por 2 vértices y 2 bordes , tiene un etiquetado elegante [3] y es hamiltoniano .
Cuentas sin diamantes y menores prohibidos
Un gráfico no tiene diamantes si no contiene un diamante como subgráfico generado . Los gráficos sin triángulos están libres de rombos, ya que cualquier rombo contiene un triángulo.
Una familia de grafos en la que cada componente conexo es un cactus se cierra bajo la operación de generar un grafo menor . Esta familia de gráficos puede ser descrita por el único menor prohibido : el diamante [4] .
Si la mariposa y el diamante son menores prohibidos, la familia de gráficos resultante es una familia de pseudobosques .
Propiedades algebraicas
El grupo de automorfismos de un diamante es un grupo de orden 4 isomorfo al grupo cuádruple de Klein , el producto directo del grupo cíclico Z /2 Z y él mismo.
El polinomio característico de un diamante es . Diamond es el único gráfico con un polinomio característico que define el gráfico por su espectro.
Véase también
- Vamos matroid
Notas
- ↑ Weisstein, Eric W. Diamond Graph en el sitio web de Wolfram MathWorld .
- ↑ ISGCI: Sistema de Información sobre Clases de Gráficos y sus Inclusiones " Lista de Pequeños Gráficos ".
- ↑ Sin-Min Lee, YC Pan y Ming-Chen Tsai. "Sobre vértices elegantes (p, p + l) -Graphs". Copia archivada (enlace no disponible) . Consultado el 16 de septiembre de 2009. Archivado desde el original el 7 de agosto de 2008.
- ↑ El-Mallah, Colbourn, 1988 , pág. 354–362.