Gráfico de Folkman

En el campo matemático de la teoría de grafos , el grafo de Folkman es un grafo 4- regular con 20 vértices y 40 aristas. Es un grafo bipartito regular con simetrías que conectan cada arista con todas las demás, pero los dos lados de su bipartición no son simétricos entre sí, lo que lo convierte en el grafo semisimétrico más pequeño posible . ^{[ 1 ]} Recibe su nombre de Jon Folkman , quien lo construyó por esta propiedad en 1967. ^{[ 2 ]}

El grafo de Folkman se puede construir utilizando aritmética modular o como el doble subdividido del grafo completo de cinco vértices . Además de investigar su simetría, también se ha estudiado como un contraejemplo para ciertas cuestiones de incrustación de grafos .

Los grafos semisimétricos se definen como grafos regulares (es decir, grafos en los que todos los vértices tocan la misma cantidad de aristas) en los que cada par de aristas es simétrico entre sí, pero algunos pares de vértices no lo son. Jon Folkman se inspiró para definir e investigar estos grafos en un artículo de 1967, después de ver un manuscrito inédito de E. Dauber y Frank Harary que daba ejemplos de grafos que cumplían la condición de simetría pero no la de regularidad. La construcción original de Folkman de este grafo era un caso especial de una construcción más general de grafos semisimétricos que utilizaba aritmética modular , basada en un número primo.${\displaystyle p}$congruente con 1 mod 4. Para cada primo de este tipo, hay un número${\displaystyle r}$de tal manera que${\displaystyle r^{2}=-1}$mod${\displaystyle p}$y Folkman utiliza aritmética modular para construir un grafo semisimétrico con${\displaystyle 2pr}$vértices. El grafo de Folkman es el resultado de esta construcción para${\displaystyle p=5}$y${\displaystyle r=2}$. ^{[ 2 ]}

Otra construcción para el grafo de Folkman comienza con el grafo completo en cinco vértices,${\displaystyle K_{5}}$. Se coloca un nuevo vértice en cada una de las diez aristas de${\displaystyle K_{5}}$, subdividiendo cada arista en un camino de dos aristas. Luego, cada uno de los cinco vértices originales de${\displaystyle K_{5}}$se duplica, reemplazándolo por dos vértices con los mismos vecinos. Los diez vértices de subdivisión forman un lado de la bipartición del grafo de Folkman, y los diez vértices en pares gemelos que provienen de los vértices duplicados de${\displaystyle K_{5}}$forman el otro lado de la bipartición. ^{[ 3 ] [ 4 ]}

Porque cada arista del resultado proviene de la mitad duplicada de una arista de${\displaystyle K_{5}}$y porque${\displaystyle K_{5}}$tiene simetrías que toman cada media arista a cada otra media arista, el resultado es transitivo en aristas. No es transitivo en vértices, porque los vértices de subdivisión no son gemelos con ningún otro vértice, lo que los hace diferentes de los vértices duplicados que vienen de${\displaystyle K_{5}}$. ^{[ 3 ]} Todo grafo semisimétrico 4-regular en el que algunos dos vértices tienen el mismo vecindario puede construirse de la misma manera, subdividiendo y luego duplicando un grafo simétrico 4-regular como${\displaystyle K_{5}}$o el grafo del octaedro . Sin embargo, también existen grafos semisimétricos 4-regulares más grandes que no tienen vértices gemelos. ^{[ 4 ] [ 5 ]}

El grupo de automorfismos del grafo de Folkman (su grupo de simetrías) combina los${\displaystyle 5!}$simetrías de${\displaystyle K_{5}}$con el${\displaystyle 2^{5}}$formas de intercambiar algunos pares de vértices duplicados, para un total de${\displaystyle 5!\cdot 2^{5}=3840}$Simetrías. Este grupo actúa transitivamente sobre las aristas del grafo de Folkman (incluye una simetría que lleva cualquier arista a cualquier otra), pero no sobre sus vértices. El grafo de Folkman es el grafo no dirigido más pequeño que es transitivo en aristas y regular, pero no transitivo en vértices . ^{[ 6 ]} Estos grafos se denominan grafos semisimétricos y fueron estudiados por primera vez por Folkman en 1967, quien descubrió el grafo de 20 vértices que ahora lleva su nombre. ^{[ 2 ]}

Como todos los grafos semisimétricos, el grafo de Folkman es bipartito . Su grupo de automorfismos incluye simetrías que llevan cualquier vértice a cualquier otro vértice que esté en el mismo lado de la bipartición, pero ninguna que lleve un vértice al otro lado de la bipartición. Aunque se puede argumentar directamente que el grafo de Folkman no es transitivo en vértices, esto también se puede explicar desde una perspectiva de teoría de grupos: sus simetrías actúan primitivamente sobre los vértices construidos como puntos de subdivisión de${\displaystyle K_{5}}$, pero de manera primitiva en los vértices construidos al duplicar los vértices de${\displaystyle K_{5}}$Cada simetría asigna un par de vértices duplicados a otro par de vértices duplicados, pero no existe ninguna agrupación de los vértices de subdivisión que se conserve mediante las simetrías. ^{[ 7 ]}

El polinomio característico del gráfico de Folkman es${\displaystyle (x-4)x^{10}(x+4)(x^{2}-6)^{4}}$. ^{[ 8 ]}

El grafo de Folkman posee un ciclo hamiltoniano y, más concretamente, una descomposición hamiltoniana en dos ciclos hamiltonianos. Como todo grafo bipartito, su número cromático es dos, y su índice cromático (el número mínimo de colores necesarios para colorear sus aristas de manera que no se encuentren dos aristas del mismo color en un vértice) es igual a su grado máximo, ^{[ 9 ]} que en este caso es cuatro. Por ejemplo, dicha coloración se puede obtener utilizando dos colores de forma alternada para cada ciclo de una descomposición hamiltoniana.

Su radio es 3 y su diámetro es 4. Si${\displaystyle v}$es uno de los vértices duplicados del${\displaystyle K_{5}}$construcción, entonces todos los demás vértices están como máximo a tres pasos de distancia de${\displaystyle v}$Sin embargo, hay pares de vértices de subdivisión de la construcción (que provienen de aristas disjuntas de${\displaystyle K_{5}}$) que están separados por cuatro pasos. Debido a que el grafo contiene muchos ciclos de 4 vértices, su circunferencia es  4, el mínimo posible para un grafo bipartito. También es 4 -conexo por vértices y 4 -conexo por aristas . Su ancho de árbol y su ancho de clique son ambos 5. ^{[ 10 ]}

El grafo de Folkman tiene género 3: puede incrustarse en un toro triple , pero no en ninguna superficie orientada más simple. ^{[ 11 ] [ 12 ]} Tiene un grosor de libro de 3, pero requiere cinco páginas para una incrustación de libro "dispersable" en la que cada página es un emparejamiento , refutando una conjetura de Frank Bernhart y Paul Kainen de que las incrustaciones de libro dispersables de grafos regulares solo necesitan un número de páginas igual a su grado. ^{[ 3 ]}

El gráfico no es 1-planar . ^{[ 13 ]}