Conde folkman
| conde folkman | |
|---|---|
| conde folkman | |
| Lleva el nombre de | J.Folkman |
| picos | veinte |
| costillas | 40 |
| Radio | 3 |
| Diámetro | cuatro |
| Circunferencia | cuatro |
| automorfismos | 3840 |
| número cromático | 2 |
| índice cromático | cuatro |
| Propiedades |
Bipartito Hamiltoniano Semisimétrico Regular Euler Perfecto |
| Archivos multimedia en Wikimedia Commons | |
El gráfico de Folkman (llamado así por John Folkman) es un gráfico regular bipartito de 4 con 20 vértices y 40 aristas [1] .
El gráfico de Folkman es hamiltoniano y tiene el número cromático 2, el índice cromático 4, el radio 3, el diámetro 4 y la circunferencia 4. También es conectado por 4 vértices , conectado por 4 bordes y perfecto . El gráfico tiene libro incrustado 3 y número de colas 2 [2] .
Propiedades algebraicas
El grupo de automorfismos de un grafo de Folkman actúa transitivamente sobre sus aristas, pero no sobre sus vértices. Es el grafo no dirigido más pequeño que es de borde transitivo y regular, pero no de vértice transitivo [3] . Dichos gráficos se denominan semisimétricos , fueron estudiados por primera vez por Folkman en 1967 y descubrió un gráfico con 20 vértices, que más tarde recibió su nombre [4] .
Como gráfico semisimétrico, el gráfico de Folkman es bipartito y su grupo de automorfismos actúa de forma transitiva en cada fracción de vértices del gráfico bipartito. En el siguiente diagrama, que muestra el número cromático de un gráfico, los vértices verdes no se pueden asignar a rojo mediante ningún automorfismo, pero cualquier vértice rojo se puede asignar a cualquier otro vértice rojo y cualquier verde a cualquier otro vértice verde.
El polinomio característico del gráfico de Folkman es .
Galería
-
El índice cromático del gráfico de Folkman es 4.
-
El número cromático de Count Folkman es 2.
-
El gráfico de Folkman es hamiltoniano .
Notas
- ↑ Gráfico de Weisstein, Eric W. Folkman en el sitio web de Wolfram MathWorld .
- ↑ Volz, 2018 .
- ↑ Skiena, 1990 , pág. 186-187.
- ↑ Folkman, 1967 , pág. 215–232.
Literatura
- Skiena S. Implementando matemáticas discretas: combinatoria y teoría de grafos con Mathematica. Lectura. — MA: Addison-Wesley, 1990.
- Jessica Walz. Ingeniería de Trazados Lineales con SAT. - Universidad de Tübingen, 2018. - (Tesis de Maestría).
- Folkman J. Gráficos simétricos de líneas regulares // Journal of Combinatorial Theory. - 1967. - T. 3 , nº. 3 . - doi : 10.1016/S0021-9800(67)80069-3 .