Grafo diamante
En el campo matemático de la teoría de grafos, el grafo diamante[1] es un grafo plano con 4 vértices y 5 aristas, cuya representación gráfica se asemeja a un diamante. El nombre del grafo está designado por la lista de clasificación de grafos pequeños del Information System on Graph Classes and their Inclusions.[2]
| Grafo diamante | ||
|---|---|---|
 Representación del grafo diamante | ||
| Vértices | 4 | |
| Aristas | 5 | |
| Radio | 1 | |
| Diámetro | 2 | |
| Cintura | 3 | |
| Automorfismos | 4 (Z/2Z×Z/2Z) | |
| Número cromático | 3 | |
| Índice cromático | 3 | |
| Propiedades |
| |
Puede ser construido a partir del grafo completo en cuatro vértices, K4 mediante la eliminación de cualquiera de una de las aristas. Otra manera de construir el grafo es a partir del grafo ciclo C4 añadiendo una arista en forma de diagonal.
Grafo libre de diamantes y contracción prohibitiva
editarUn grafo es libre de diamantes[3] si no contiene al grafo diamante como subgrafo inducido. Un grafo libre de triángulos es necesariamente un grafo libre de diamantes, al contener el grafo diamante un triángulo C3. La conjetura de Hougardy está probada para grafos libres de diamantes.[4]
La familia de grafos conocida como grafos cactus se caracterizan por no tener al grafo diamante como subgrafo mediante una contracción por aristas.[5]
Los grafos diamantes y los grafos mariposas son contracciones por aristas prohibitivas para la familia de grafos llamada pseudobosque, y es una característica de esta clase de grafos.
Propiedades generales
editarEs plano, ya que puede representarse en el plano sin que sus aristas de crucen. Es 3-conexo por vértices, no tiene vértice de corte. Es hamiltoniano. Es 3-conexo por aristas. Al tener dos vértices de grado impar (3) no es euleriano, aunque acepta un camino Euleriano.
Coloración
editarEl número cromático del grafo pez es 3. Es decir, que es posible colorear los vértices con tres colores tal que dos vértices conectados por una arista tengan siempre colores diferentes.
El índice cromático del grafo es 3. Esto es, existe una 3-coloración por aristas del grafo tal que dos aristas incidentes a un mismo vértice son siempre de colores diferentes.
El polinomio cromático es igual a .
Propiedades algebraicas
editarEl grupo de automorfismo del grafo pez es un grupo abeliano de orden 4 isomorfo al grupo de KleinZ/2Z×Z/2Z.
El polinomio característico del grafo es: .
Referencias
editar- ↑ Eric W. Weisstein, Diamond Graph (MathWorld) (en inglés)
- ↑ ISGCI (Information System on Graph Classes and their Inclusions), Lista de grafos pequeños (caché) (en inglés).
- ↑ DANKELMANN Peter; HELLWIG Angelika and VOLKMANN Lutz, On the connectivity of diamond-free graphs, Discrete applied mathematics, 2007, vol. 155, no16, pp. 2111-2117. (en inglés)
- ↑ Kezdy A.E, Scobee M. "A proof of Hougardy's conjecture for diamond-free graphs". Discrete Mathematics, Volume 240, 1, 28 septembre 2001, pp. 83-95(13) (en inglés) .
- ↑ El-Mallah, Ehab; Colbourn, Charles J. (1988). «The complexity of some edge deletion problems». IEEE Transactions on Circuits and Systems 35 (3): 354-362. doi:10.1109/31.1748. (en inglés).
Datos: Q3115555
Multimedia: Diamond graph / Q3115555
