Gráfico circular

En teoría de grafos, un grafo circulante es un grafo no dirigido que tiene un grupo de simetría cíclica que incluye una simetría que lleva cualquier vértice a cualquier otro vértice .

Definiciones equivalentes

Los gráficos circulantes se pueden definir de varias formas equivalentes [1] :

Un automorfismo de grupo de gráficos contiene un subgrupo cíclico que actúa transitivamente en los vértices del gráfico.
El grafo tiene una matriz de adyacencia que es una circulante .
$norte$ Los vértices del gráfico se pueden numerar de 0 a n − 1 de tal manera que si dos vértices con números y son adyacentes, entonces dos vértices cualesquiera con números y ( z − x + y ) mod n también son adyacentes. $X$ $y$ $z$
Se puede dibujar un gráfico (con posibles intersecciones de bordes) de tal manera que sus vértices se encuentren en las esquinas de un polígono regular, y cualquier rotación del polígono en sí mismo es una simetría del dibujo (obtenemos el mismo dibujo).

Ejemplos

Cualquier ciclo es un gráfico circulante, como lo es cualquier corona .

Los gráficos de orden de Paley (donde es un primo congruente con 1 módulo 4) son gráficos en los que los vértices son números de 0 a n − 1 y dos vértices son adyacentes si la diferencia de los números correspondientes es un residuo cuadrático módulo . Debido al hecho de que la presencia o ausencia de un borde depende solo de la diferencia en los números de vértice del módulo , cualquier gráfico de Paley es un gráfico circulante. $norte$ $norte$ $norte$ $norte$

Cualquier escalera de Möbius es un grafo circulante, como lo es cualquier grafo completo . Un grafo bipartito completo es circulante si ambas partes tienen el mismo número de vértices.

Si dos números y son coprimos , entonces el gráfico de torre de m × n (un gráfico que tiene un vértice en cada celda de un tablero de ajedrez de m × n y una arista entre dos celdas cualesquiera si la torre puede moverse de una celda a otra en un solo movimiento ) es un grafo circulante. Esto es consecuencia del hecho de que sus simetrías contienen el grupo cíclico {{{1}}} como subgrupo . Como generalización de este caso, el producto directo de grafos entre cualquier grafo circulante con vértices y da como resultado un grafo circulante [1] . $metro$ $norte$ $metro$ $norte$

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

Estudio de caso

Un grafo circulante (o , o ) con saltos se define como un grafo con nodos numerados y cada nodo es adyacente a 2k nodos módulo . $C_{n}^{s_{1},\ldots,s_{k))$ $C_{n}(s_{1},\ldots,s_{k})$ $circ(n:s_{1},\ldots,s_{k})$ ${\displaystyle s_{1},\ldots,s_{k))$ $norte$ $0,1,\ldots,n-1$ $i$ ${\displaystyle i\pm s_{1},\ldots,i\pm s_{k))$ $norte$

El grafo es conexo si y solo si mcd . $C_{n}^{s_{1},\ldots,s_{k))$ $(n,s_{1},\ldots,s_{k})=1$

Si son enteros fijos, entonces el número de árboles de expansión , donde satisface la relación de recurrencia de orden . ${\displaystyle 1\leq s_{1}<\cdots <s_{k))$ ${\displaystyle t(C_{n}^{s_{1},\ldots,s_{k)))=na_{n}^{2))$ $un$ ${\ estilo de visualización 2^{s_{k}-1}}$
- En particular, , donde es el
n-ésimo número de Fibonacci . ${\displaystyle t(C_{n}^{1,2})=nF_{n}^{2))$ $F_{n}$

Circulantes autocomplementarios

Un gráfico autocomplementario es aquel en el que la eliminación de los bordes existentes y la adición de los que faltan dan como resultado un gráfico isomorfo al original.

Por ejemplo, un gráfico cíclico con cinco vértices es autocomplementario y también circulante. De manera más general, cualquier gráfico de Paley es un gráfico circulante autocomplementario [3] . Horst Sachs demostró que si un número tiene la propiedad de que cualquier divisor primo es congruente con 1 módulo 4, entonces existe un grafo circulante autocomplementario con vértices. Él planteó la hipótesis de que esta condición es necesaria, es decir, para otros valores, no existen grafos circulantes autocomplementarios [1] [3] . La conjetura fue probada 40 años después por Wilfred [1] . $norte$ $norte$ $norte$ $norte$

Hipótesis de Adams

Definimos la numeración circulante de un grafo circulante como marcar los vértices del grafo con números de 0 a n − 1 de tal manera que si dos vértices y son adyacentes, entonces dos vértices cualesquiera con números y ( z − x + y ) mod n también son adyacentes. De manera equivalente, una numeración circulante es una numeración de vértices tal que la matriz de adyacencia de un gráfico es una matriz circulante. $X$ $y$ $z$

Sea un entero coprimo c , y sea cualquier entero. Entonces la función lineal ax + b transforma la numeración circulante en otra numeración circulante. András Ádám conjeturó que una aplicación lineal es la única forma de volver a numerar los vértices de un gráfico que conserva la propiedad de circulación. Es decir, si y son dos gráficas circulantes isomorfas con diferente numeración, entonces hay una transformación lineal que transforma la numeración para en la numeración para . Sin embargo, resultó que la hipótesis de Adam no es correcta. Los gráficos con 16 vértices en cada uno sirven como contraejemplo ; el vértice en está conectado a seis vecinos x ± 1 , x ± 2 y x ± 7 (mod 16), mientras que en seis vecinos son x ± 2 , x ± 3 y x ± 5 (mod 16). Estos dos gráficos son isomorfos, pero su isomorfismo no se puede obtener mediante una transformación lineal. [una] $a$ $norte$ $b$ $GRAMO$ $H$ $GRAMO$ $H$ $GRAMO$ $H$ $X$ $GRAMO$ $H$

Notas

↑ 1 2 3 4 5 V. Wilfred. Graph Theory and its Applications (Universidad de Anna, Chennai, 14 al 16 de marzo de 2001) / editores: R. Balakrishnan, G. Sethuraman, Robin J. Wilson. - Alpha Science, 2004. - S. 34-36 .
↑ Small Ramsey Numbers Archivado el 18 de enero de 2012 en Wayback Machine , Stanisław P. Radziszowski, Electronic J. Combinatorics , encuesta dinámica actualizada en 2009.
↑ 12 Horst Sachs. Über selbstkomplementäre Graphen // Publicationes Mathematicae Debrecen. - 1962. - T. 9 . - S. 270-288 .

Enlaces

Weisstein, Eric W. Circulant Graph (inglés) en el sitio web de Wolfram MathWorld .