Conde de Meredith
| Conde de Meredith | |
|---|---|
| Lleva el nombre de | chico meredith |
| picos | 70 |
| costillas | 140 |
| Diámetro | ocho |
| Circunferencia | 5 |
| automorfismos | 38698352640 |
| número cromático | 3 |
| índice cromático | 5 |
| Propiedades | Euler |
| grosor del libro | 3 |
| Número de colas | 2 |
| Archivos multimedia en Wikimedia Commons | |
El grafo de Meredith es un grafo no dirigido regular de 4 con 70 vértices y 140 aristas, descubierto por Guy Meredith en 1973 [1] .
El gráfico de Meredith está conectado por 4 vértices y por 4 aristas . Tiene un número cromático de 3, un índice cromático de 5, un radio de 7, un diámetro de 8, una circunferencia de 4 y no es hamiltoniano [2] . El gráfico tiene grosor de libro 3 y número de colas 2 [3] .
Publicado en 1973, el gráfico proporcionó un contraejemplo a la conjetura de Crispin Nash-Williams de que cualquier gráfico conectado a 4 vértices regulares siempre es hamiltoniano [4] [5] . Sin embargo, Tatt demostró que todos los gráficos planares conectados en 4 son hamiltonianos [6] .
El polinomio característico del gráfico de Meredith es
.
Galería
-
El número cromático del conde de Meredith es 3.
-
El índice cromático del conde de Meredith es 5.
Notas
- ↑ Weisstein, gráfico de Eric W. Meredith en el sitio web de Wolfram MathWorld .
- ↑ Bondy JA, Murty USR Graph Theory. - Springer, 2007. - Pág. 470.
- ↑ Jessica Wolz, Diseños lineales de ingeniería con SAT . Tesis de Maestría, Universidad de Tübingen, 2018
- ↑ Meredith GHJ Regular 4-Valent 4-Connected Non-hamiltonian Non-4-Edge-Colorable Graphs // J. Combin. ju.. - 1973. - Emisión. B 14 . - S. 55-60 .
- ↑ Bondy JA, Murty USR Graph Theory with Applications. - Nueva York: Holanda Septentrional, 1976. - Pág. 239.
- ↑ Progreso reciente en combinatoria / Tutte W. Literatura T .. - Nueva York: Academic Press, 1969.
Enlaces
- Sitio web de AE Brouwer: The Armanios-Wells graph Archivado el 14 de abril de 2018 en Wayback Machine .