En teoría de grafos , un gráfico circulante es un gráfico no dirigido sobre el que actúa un grupo cíclico de simetrías que lleva cualquier vértice a cualquier otro vértice . A veces se le llama gráfico cíclico , [1] pero este término tiene otros significados.
Los gráficos circulantes se pueden describir de varias formas equivalentes: [2]
Cada gráfico de ciclo es un gráfico circulante, al igual que cada gráfico de corona con 2 vértices de módulo 4.
Las gráficas de Paley de orden n (donde n es un número primo congruente con 1 módulo 4 ) es una gráfica en la que los vértices son los números del 0 al n − 1 y dos vértices son adyacentes si su diferencia es un residuo cuadrático módulo n . Dado que la presencia o ausencia de una arista depende únicamente de la diferencia módulo n de dos números de vértice, cualquier gráfico de Paley es un gráfico circulante.
Toda escalera de Möbius es un grafo circulante, como lo es todo grafo completo . Un grafo bipartito completo es un grafo circulante si tiene el mismo número de vértices en ambos lados de su bipartición.
Si dos números m y n son primos relativos , entonces la gráfica de la torre m × n (una gráfica que tiene un vértice para cada cuadrado de un tablero de ajedrez m × n y una arista para cada dos casillas entre las que una torre de ajedrez puede moverse en un solo movimiento) es un gráfico circulante. Esto se debe a que sus simetrías incluyen como subgrupo al grupo cíclico C mn C m × C n . De manera más general, en este caso, el producto tensorial de gráficos entre cualquier m - y n -circulantes de vértices es en sí mismo un circulante. [2]
Muchos de los límites inferiores conocidos de los números de Ramsey provienen de ejemplos de gráficos circulantes que tienen pequeños grupos máximos y pequeños conjuntos máximos independientes . [1]
El gráfico circulante con saltos se define como el gráfico con nodos etiquetados donde cada nodo i es adyacente a 2 k nodos .
Un gráfico autocomplementario es un gráfico en el que reemplazar cada arista por un no borde y viceversa produce un gráfico isomórfico . Por ejemplo, un gráfico de ciclo de cinco vértices es autocomplementario y también es un gráfico circulante. De manera más general, todo gráfico de Paley de orden primo es un gráfico circulante autocomplementario. [4] Horst Sachs demostró que, si un número n tiene la propiedad de que todo factor primo de n es congruente con 1 módulo 4 , entonces existe un circulante autocomplementario con n vértices. Conjeturó que esta condición también es necesaria: que ningún otro valor de n permita que exista un circulante autocomplementario. [2] [4] La conjetura fue probada unos 40 años después, por Vilfred. [2]
Defina una numeración circulante de un gráfico circulante como un etiquetado de los vértices del gráfico con los números del 0 al n − 1 de tal manera que, si dos vértices numerados xey son adyacentes , entonces cada dos vértices numerados z y ( z − x + y ) mod n son adyacentes. De manera equivalente, una numeración circulante es una numeración de los vértices para los cuales la matriz de adyacencia del gráfico es una matriz circulante.
Sea a un número entero que es primo relativo con n y sea b cualquier número entero. Entonces la función lineal que lleva un número x a ax + b transforma una numeración circulante en otra numeración circulante. András Ádám conjeturó que estos mapas lineales son las únicas formas de renumerar un grafo circulante preservando al mismo tiempo la propiedad circulante: es decir, si G y H son grafos circulantes isomórficos, con numeraciones diferentes, entonces hay un mapa lineal que transforma la numeración de G en la numeración de H . Sin embargo, ahora se sabe que la conjetura de Ádám es falsa. Un contraejemplo lo dan los gráficos G y H con 16 vértices cada uno; un vértice x en G está conectado a los seis vecinos x ± 1 , x ± 2 y x ± 7 módulo 16, mientras que en H los seis vecinos son x ± 2 , x ± 3 y x ± 5 módulo 16. Estos dos Los gráficos son isomórficos, pero su isomorfismo no puede realizarse mediante un mapa lineal. [2]
La conjetura de Toida refina la conjetura de Ádám al considerar solo una clase especial de gráficos circulantes, en los que todas las diferencias entre los vértices de los gráficos adyacentes son primos relativos con respecto al número de vértices. Según esta refinada conjetura, estos gráficos circulantes especiales deberían tener la propiedad de que todas sus simetrías provienen de simetrías del grupo aditivo subyacente de números módulo n . Fue probado por dos grupos en 2001 y 2002. [5] [6]
Existe un algoritmo de reconocimiento de tiempo polinomial para gráficos circulantes, y el problema de isomorfismo para gráficos circulantes se puede resolver en tiempo polinomial. [7] [8]
