Circunferencia (teoría de grafos)

La circunferencia en la teoría de grafos es la longitud del ciclo más pequeño contenido en un gráfico dado [1] . Si el gráfico no contiene ciclos (es decir, es un gráfico acíclico), su circunferencia es, por definición, igual a infinito [2] . Por ejemplo, un (cuadrado) de 4 ciclos tiene un perímetro 4. Una red cuadrada también tiene un perímetro 4 y una cuadrícula triangular tiene un perímetro 3. Un gráfico con un perímetro cuatro o más no tiene triángulos .

Células

Los gráficos cúbicos (todos los vértices tienen grado tres) con la menor circunferencia posible se conocen como -celdas (o como (3, )-celdas). El gráfico de Petersen es el único de 5 celdas (el gráfico cúbico más pequeño con una circunferencia de 5), el gráfico de Heawood es el único de 6 celdas, el gráfico de McGee es el único de 7 celdas y el gráfico de Tutt-Coxeter es el único de 8 celdas. celda [3] . Puede haber varias celdas (gráficas) para una circunferencia dada. Por ejemplo, hay tres celdas de 10 no isomorfas, cada una con 70 vértices: la celda de 10 de Balaban , el gráfico de Harris y el gráfico de Harris-Wong . $gramo$ $gramo$ $gramo$

El gráfico de Petersen tiene una circunferencia de 5
El gráfico de Heawood tiene una circunferencia de 6
Earl McGee tiene una circunferencia de 7
El gráfico de Tutta-Coxeter ( 8 celdas de Tatta ) tiene una circunferencia de 8

Circunferencia y coloración del gráfico

Para cualquier número entero positivo , hay un gráfico con circunferencia y número cromático . Por ejemplo, el gráfico de Grötzsch es un gráfico sin triángulos y tiene el número cromático 4, y la repetición de la construcción myzelskiana utilizada para crear el gráfico de Grötzsch muchas veces produce gráficos sin triángulos con un número cromático arbitrariamente grande. Pal Erdős demostró este teorema utilizando el método probabilístico [4] . $k$ $GRAMO$ ${\ Displaystyle g (G) \ geq k}$ ${\ estilo de visualización \ chi (G) \ geq k}$

plano de prueba . Llamamos ciclos de longitud a lo sumo cortos, y conjuntos con o más vértices grandes. Para probar el teorema, basta con encontrar un gráfico sin ciclos cortos y grandes conjuntos independientes de vértices. Entonces, los conjuntos de colores en la coloración no serán grandes y, como resultado, se requerirán colores para colorear. $k$ ${\ estilo de visualización | G | / k}$ $GRAMO$ $k$

Para encontrar tal gráfico, fijaremos la probabilidad de elección igual a . Para v pequeña , solo ocurre una pequeña cantidad de ciclos cortos. Si ahora eliminamos un vértice de cada ciclo, el gráfico resultante no tendrá ciclos cortos y su número de independencia no será menor que el del gráfico [1] . $pags$ ${\ estilo de visualización n^{\ épsilon -1}}$ $\epsilon$ $GRAMO$ $H$ $GRAMO$

Conceptos relacionados

La circunferencia impar y la circunferencia par de un gráfico son las longitudes del ciclo impar y el ciclo par más pequeños, respectivamente.

La circunferencia de un gráfico es la longitud del ciclo más largo, no el más corto.

Pensar en la duración del ciclo no trivial más pequeño puede verse como una generalización de la sístole de 1 o más en la geometría sistólica .

Notas

↑ 1 2 Reinhard Distel. Teoría de grafos. - Novosibirsk: Editorial del Instituto de Matemáticas, 2002.
↑ Circunferencia -- Wolfram MathWorld.
↑ Andries E. Brouwer. jaulas Suplemento electrónico del libro Distance-Regular Graphs (Brouwer, Cohen, Neumaier 1989, Springer-Verlag).
↑ Paul Erdős. Teoría de grafos y probabilidad // Canadian Journal of Mathematics. - 1959. - T. 11 . - S. 34-38 . -doi : 10.4153 / CJM-1959-003-9 .