En el campo matemático de la teoría de grafos , el grafo de Folkman , que lleva el nombre de Jon Folkman , es un grafo bipartito 4- regular con 20 vértices y 40 aristas. [1]
Gráfico de Folkman | |
---|---|
Lleva el nombre de | Jon Folkman |
Vértices | 20 |
Bordes | 40 |
Radio | 3 |
Diámetro | 4 |
Circunferencia | 4 |
Automorfismos | 3840 |
Número cromático | 2 |
Índice cromático | 4 |
Espesor del libro | 3 |
Número de cola | 2 |
Propiedades | Hamiltoniano Regular Bipartito Semi-simétrico Perfecto Euleriano |
Tabla de gráficos y parámetros |
La gráfica de Folkman es hamiltoniana y tiene número cromático 2, índice cromático 4, radio 3, diámetro 4 y circunferencia 4. También es una gráfica perfecta de 4 vértices y 4 aristas . Tiene un grosor de libro 3 y un número de cola 2. [2]
Propiedades algebraicas
El grupo de automorfismo del gráfico de Folkman actúa de forma transitiva en sus bordes pero no en sus vértices. Es el gráfico no dirigido más pequeño que es transitivo por el borde y regular, pero no transitivo por el vértice . [3] Estos gráficos se denominan gráficos semi-simétricos y fueron estudiados por primera vez por Folkman en 1967, quien descubrió el gráfico de 20 vértices que ahora lleva su nombre. [4]
Como gráfico semisimétrico, el gráfico de Folkman es bipartito y su grupo de automorfismo actúa de forma transitiva en cada uno de los dos conjuntos de vértices de la bipartición. En el siguiente diagrama que indica el número cromático del gráfico, los vértices verdes no se pueden asignar a los rojos mediante ningún automorfismo, pero cualquier vértice rojo se puede asignar a cualquier otro vértice rojo y cualquier vértice verde se puede asignar 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 del gráfico de Folkman es 2.
El gráfico de Folkman es hamiltoniano .
Referencias
- ^ Weisstein, Eric W. "Gráfico de Folkman" . MathWorld .
- ^ Wolz, Jessica; Diseños lineales de ingeniería con SAT. Tesis de maestría, Universidad de Tübingen, 2018
- ^ Skiena, S. Implementación de matemáticas discretas: combinatoria y teoría de grafos con Mathematica. Reading, MA: Addison-Wesley, págs. 186-187, 1990
- ^ Folkman, J. (1967), "Gráficos simétricos de líneas regulares", Journal of Combinatorial Theory , 3 (3): 215-232, doi : 10.1016 / S0021-9800 (67) 80069-3