Hispanopedia Wiki
Articulo de referencia

Jaula (teoría de grafos)

La jaula Tutte (3,8) . En el campo matemático de la teoría de grafos , una jaula es un grafo regular que tiene el menor número posible de vértices para su circunferencia . Forma...

Hispanopedia WikiContenido en espanolLectura gratuita
La jaula Tutte (3,8) .

En el campo matemático de la teoría de grafos , una jaula es un grafo regular que tiene el menor número posible de vértices para su circunferencia .

Formalmente, un ( r , g ) -grafo se define como un grafo en el que cada vértice tiene exactamente r vecinos y en el que el ciclo más corto tiene una longitud exactamente g . Una ( r , g ) -jaula es un ( r , g ) -grafo con el menor número posible de vértices, entre todos los ( r , g ) -grafos . Una (3, g ) -jaula se denomina a menudo g -jaula .

Se sabe que existe un ( r , g ) -grafo para cualquier combinación de r ≥ 2 y g ≥ 3. De ello se deduce que existen todas las ( r , g ) -jaulas .

Si existe un grafo de Moore con grado r y circunferencia g , debe ser una jaula. Además, los límites de los tamaños de los grafos de Moore se generalizan a las jaulas: cualquier jaula con circunferencia impar g debe tener al menos

1 + a ∑ i = 0 ( gramo − 3 ) / 2 ( a − 1 ) i {\displaystyle 1+r\sum _{i=0}^{(g-3)/2}(r-1)^{i}}

vértices, y cualquier jaula con circunferencia par g debe tener al menos

2 ∑ i = 0 ( gramo − 2 ) / 2 ( a − 1 ) i {\displaystyle 2\suma _{i=0}^{(g-2)/2}(r-1)^{i}}

vértices. Cualquier ( r , g ) -grafo con exactamente esta cantidad de vértices es, por definición, un grafo de Moore y, por lo tanto, automáticamente una jaula.

Pueden existir múltiples jaulas para una combinación dada de r y g . Por ejemplo, hay tres jaulas (3, 10) no isomorfas , cada una con 70 vértices: la jaula de 10 de Balaban , el grafo de Harries y el grafo de Harries–Wong . Pero solo hay una jaula (3, 11) : la jaula de 11 de Balaban (con 112 vértices).

Jaulas conocidas

Un grafo 1-regular no tiene ciclo, y un grafo 2-regular conexo tiene circunferencia igual a su número de vértices, por lo que las jaulas solo son de interés para r ≥ 3. La jaula ( r ,3) es un grafo completo K r  + 1 en r  + 1 vértices, y la jaula ( r ,4) es un grafo bipartito completo K r , r en 2 r vértices.

Las jaulas notables incluyen:

Los números de vértices en las jaulas conocidas ( r , g ), para valores de r > 2 y g > 2, distintos de los planos proyectivos y los polígonos generalizados, son:

Asintóticos

Para valores grandes de g , el límite de Moore implica que el número n de vértices debe crecer al menos exponencialmente en función de g . De manera equivalente, g puede ser como máximo proporcional al logaritmo de n . Más precisamente,

gramo ≤ 2 registro a − 1 ⁡ norte + Oh ( 1 ) . {\displaystyle g\leq 2\log _{r-1}n+O(1).}

Se cree que este límite es estricto o casi estricto (Bollobás y Szemerédi 2002). Los límites inferiores más conocidos de g también son logarítmicos, pero con un factor constante más pequeño (lo que implica que n crece exponencialmente pero a una tasa mayor que el límite de Moore). Específicamente, la construcción de grafos de Ramanujan definidos por Lubotzky, Phillips y Sarnak (1988) satisfacen el límite.

gramo ≥ 4 3 registro a − 1 ⁡ norte + Oh ( 1 ) . {\displaystyle g\geq {\frac {4}{3}}\log _{r-1}n+O(1).}

Este límite fue mejorado ligeramente por Lazebnik, Ustimenko y Woldar (1995).

Es poco probable que estos gráficos sean en sí mismos jaulas, pero su existencia da un límite superior al número de vértices necesarios en una jaula.

Referencias

Obtenido de "https://es.wikipedia.org/w/index.php?title=Cage_(teoría_de_grafos)&oldid=1240181681"