Gráfico circulante

En teoría de grafos , un grafo circulante es un grafo 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 lo denomina grafo cíclico , ^[1] pero este término tiene otros significados.

Definiciones equivalentes

Los gráficos circulantes se pueden describir de varias formas equivalentes: ^[2]

El grupo de automorfismos del grafo incluye un subgrupo cíclico que actúa transitivamente sobre los vértices del grafo. En otras palabras, el grafo tiene un automorfismo que es una permutación cíclica de sus vértices.
El gráfico tiene una matriz de adyacencia que es una matriz circulante .
Los $n$ vértices del grafo se pueden numerar de 0 a $n - 1$ de tal manera que, si dos vértices numerados $x$ y $(x + d) mod n$ son adyacentes, entonces cada dos vértices numerados $z$ y $(z + d) mod n$ son adyacentes.
El gráfico se puede dibujar (posiblemente con cruces) de modo que sus vértices se encuentren en las esquinas de un polígono regular , y cada simetría rotacional del polígono es también una simetría del dibujo.
El gráfico es un gráfico de Cayley de un grupo cíclico . ^[3]

Ejemplos

Todo gráfico de ciclo es un gráfico circulante, como lo es todo gráfico de corona con número de vértices congruentes a 2 módulo 4.

Los grafos de Paley de orden $n$ (donde $n$ es un número primo congruente con 1 módulo 4 ) son grafos en los que los vértices son los números de 0 a $n - 1$ y dos vértices son adyacentes si su diferencia es un residuo cuadrático módulo $n$ . Como la presencia o ausencia de una arista depende únicamente de la diferencia módulo $n$ de dos números de vértice, cualquier grafo de Paley es un grafo circulante.

Toda escalera de Möbius es un grafo circulante, al igual que 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 entre sí , entonces el grafo de la torre $m \times n$ (un grafo que tiene un vértice por cada casilla de un tablero de ajedrez $m$ $\times$ $n$ y una arista por cada dos casillas entre las que una torre puede moverse en un solo movimiento) es un grafo 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 grafos entre cualesquiera circulantes de $m$ y $n$ vértices es en sí mismo un circulante. ^[2] ${\estilo de visualización \simeq}$

Muchos de los límites inferiores conocidos de los números de Ramsey provienen de ejemplos de gráficos circulantes que tienen camarillas máximas pequeñas y conjuntos independientes máximos pequeños . ^[1]

Un ejemplo específico

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 . $C_{n}^{s_{1},\ldots ,s_{k}}$ $s_{1},\ldots ,s_{k}$ ${\estilo de visualización n}$ $0,1,\ldots ,n-1$ $i\pm s_{1},\ldots ,i\pm s_{k}\mod n$

El gráfico es conexo si y sólo si . $C_{n}^{s_{1},\ldots ,s_{k}}$ $\mcd(n,s_{1},\ldots ,s_{k})=1$
Si son números enteros fijos , entonces el número de árboles de expansión donde satisface una relación de recurrencia de orden . $1\leq s_{1}<\cdots <s_{k}$ $t(C_{n}^{s_{1},\ldots ,s_{k}})=na_{n}^{2}$ $a_{n}$ $Estilo de visualización 2^{s_{k}-1}}$
- En particular, ¿dónde está el n -ésimo número de Fibonacci ? $t(C_{n}^{1,2})=nF_{n}^{2}$ $Estilo de visualización F_{n}$

Circulantes autocomplementarios

Un grafo autocomplementario es un grafo en el que al reemplazar cada arista por una que no sea arista y viceversa se produce un grafo isomorfo . Por ejemplo, un grafo de ciclo de cinco vértices es autocomplementario y también es un grafo circulante. De manera más general, todo grafo de Paley de orden primo es un grafo 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 demostrada unos 40 años después por Vilfred. ^[2]

La conjetura de Ádám

Definamos una numeración circulante de un grafo circulante como una etiqueta de los vértices del grafo con los números de 0 a $n - 1$ de tal manera que, si dos vértices numerados $x$ $e$ y 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 grafo es una matriz circulante.

Sea $a$ un entero que es primo relativo con $n$ , y sea $b$ un entero cualquiera. 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 estas aplicaciones lineales son las únicas formas de renumerar un grafo circulante mientras se preserva la propiedad circulante: es decir, si $G$ y $H$ son grafos circulantes isomorfos, con numeraciones diferentes, entonces hay una aplicación lineal que transforma la numeración para $G$ en la numeración para $H$ . Sin embargo, ahora se sabe que la conjetura de Ádám es falsa. Un contraejemplo lo dan los grafos $G$ y $H$ con 16 vértices cada uno; Un vértice $x$ en $G$ está conectado a los seis vecinos $x \pm 1$ , $x \pm 2$ y $x \pm 7$ módulo 16, mientras que en $H$ los seis vecinos son $x \pm 2$ , $x \pm 3$ y $x \pm 5$ módulo 16. Estos dos gráficos son isomorfos, pero su isomorfismo no se puede realizar mediante una función lineal. ^[2]

La conjetura de Toida refina la conjetura de Ádám considerando solo una clase especial de grafos circulantes, en los que todas las diferencias entre los vértices de los grafos adyacentes son primos entre sí respecto del número de vértices. Según esta conjetura refinada, estos grafos 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$ . Esto fue demostrado por dos grupos en 2001 y 2002. ^[5]^[6]

Preguntas algorítmicas

Existe un algoritmo de reconocimiento en tiempo polinomial para gráficos circulantes, y el problema de isomorfismo para gráficos circulantes se puede resolver en tiempo polinomial. ^[7]^[8]

Referencias

^ ab Small Ramsey Numbers, Stanisław P. Radziszowski, Electronic J. Combinatorics , encuesta dinámica 1, actualizada en 2014.
^ abcde Vilfred, V. (2004), "Sobre los grafos circulantes", en Balakrishnan, R.; Sethuraman, G.; Wilson, Robin J. (eds.), Graph Theory and its Applications (Anna University, Chennai, 14-16 de marzo de 2001), Alpha Science, págs. 34-36.
^ Alspach, Brian (1997), "Isomorfismo y grafos de Cayley en grupos abelianos", Graph symmetry (Montreal, PQ, 1996), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 497, Dordrecht: Kluwer Acad. Publ., págs. 1–22, MR 1468786.
^ ab Sachs, Horst (1962). "Über selbstkomplementäre Graphen". Publicaciones Mathematicae Debrecen . 9 : 270–288. SEÑOR 0151953..
^ Muzychuk, Mikhail; Klin, Mikhail; Pöschel, Reinhard (2001), "El problema del isomorfismo para grafos circulantes a través de la teoría de anillos de Schur", Códigos y esquemas de asociación (Piscataway, NJ, 1999) , DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 56, Providence, Rhode Island: American Mathematical Society, págs. 241–264, MR 1816402
^ Dobson, Edward; Morris, Joy (2002), "La conjetura de Toida es verdadera", Electronic Journal of Combinatorics , 9 (1): R35:1–R35:14, MR 1928787
^ Muzychuk, Mikhail (2004). "Una solución del problema del isomorfismo para grafos circulantes". Proc. London Math. Soc . 88 : 1–41. doi :10.1112/s0024611503014412. MR 2018956.
^ Evdokimov, Sergei; Ponomarenko, Ilia (2004). "Reconocimiento y verificación de un isomorfismo de grafos circulantes en tiempo polinomial". St. Petersburg Math. J. 15 : 813–835. doi : 10.1090/s1061-0022-04-00833-7 . MR 2044629.

Enlaces externos

Weisstein, Eric W. "Gráfico circulante". MundoMatemático .