Jaula (teoría de grafos)

En el área matemática de la teoría de grafos, una jaula es un grafo regular que tiene la menor cantidad de vértices posible para su cintura.

Formalmente, un (r,g)-grafo se define como un grafo en el cual cada vértice tiene exactamente r vecinos, y en el cual el ciclo más corto tiene una longitud exactamente de g. Se sabe que existen (r,g)-grafos para cualquier combinación de r ≥ 2 y g ≥ 3. Una (r,g)-jaula es un (r,g)-grafo con el menor número de vértices posible, entre todos los (r,g)-grafos.

Si existe un grafo de Moore de grado r y cintura g, debe ser una jaula. Es más, los límites de los tamaños de los grafos de Moore se generalizan a las jaulas: cualquier jaula de cintura impar g debe tener como mínimo

1+r\sum _{i=0}^{(g-3)/2}(r-1)^{i}

vértices, y cualquier jaula de cintura par g debe tener como mínimo

2\sum _{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 varias jaulas para una combinación dada de r y g. Por ejemplo, hay tres (3,10)-jaulas no isomórficas, cada una con 70 vértices : la 10-jaula de Balaban, el grafo de Harries y el grafo de Harries-Wong. Pero existe solo una (3,11)-jaula : la 11-jaula de Balaban (con 112 vértices).

Jaulas conocidas

Un grafo de grado uno no tiene ciclos, y un grafo conexo de grado dos tiene una cintura igual al número de sus vértices, por lo que las jaulas solo son de interés para r ≥ 3. La (r,3)-jaula es un grafo completo K_r+1 sobre r+1 vértices, y la (r,4)-jaula es un grafo bipartito completo K_r,r sobre 2r vértices.

Otras jaulas destacables son los grafos de Moore:

(3,5)-jaula: el grafo de Petersen, 10 vértices
(3,6)-jaula: el grafo de Heawood, 14 vértices
(3,8)-jaula: el grafo de Tutte–Coxeter, 30 vértices
(3,10)-jaula: la 10-jaula de Balaban, 70 vértices
(4,5)-jaula: el grafo de Robertson, 19 vértices
(7,5)-jaula: el grafo de Hoffman–Singleton, 50 vértices.
Cuando r-1 es una potencia prima, las (r,6) jaulas son los grafos de incidencia de los planos proyectivos.
Cuando r-1 es una potencia prima, las (r,8) y (r,12) jaulas son polígonos generalizados.

El número de vértices en las (r,g)-jaulas conocidas, para valores de r > 2 y g > 2, aparte de planos proyectivos y polígonos generalizados, es:

r = 3:	4	6	10	14	24	30	58	70	112	126
g:	3	4	5	6	7	8	9	10	11	12
r = 4:	5	8	19	26	67	80				728
r = 5:	6	10	30	42		170				2730
r = 6:	7	12	40	62		312				7812
r = 7:	8	14	50	90

Asintótica

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

g\leq 2\log _{r-1}n+O(1).

Se cree que esta cota es estrecha o está cerca de ser estrecha (Bollobás y Szemerédi, 2002). Las cotas inferiores más conocidas de g son también logarítmicas, pero con un factor constante menor (lo que implica que n crece exponencialmente pero a un ritmo más alto que la cota de Moore). Específicamente, los grafos de Ramanujan (Lubotzky, Phillips y Sarnak, 1988) satisfacen la cota

g\geq {\frac {4}{3}}\log _{r-1}n+O(1).

Es poco probable que estos grafos sean en sí mismos jaulas, pero su existencia pone un límite superior para el número de vértices necesarios en una jaula.

Referencias

Biggs, Norman (1993), Algebraic Graph Theory (2nd edición), Cambridge Mathematical Library, pp. 180-190, ISBN 0-521-45897-8 ..
Bollobás, Béla; Szemerédi, Endre (2002), «Girth of sparse graphs», Journal of Graph Theory 39 (3): 194-200, MR 1883596, doi:10.1002/jgt.10023 ..
Exoo, G; Jajcay, R (2008), «Dynamic Cage Survey», Electronic Journal of Combinatorics (Dynamic Survey), DS16, archivado desde el original el 1 de enero de 2015, consultado el 18 de agosto de 2014 ..
Erdõs, Paul; Rényi, Alfréd; Sós, Vera T. (1966), «On a problem of graph theory», Studia Sci. Math. Hungar. 1: 215-235, archivado desde el original el 9 de marzo de 2016, consultado el 18 de agosto de 2014 ..
Hartsfield, Nora; Ringel, Gerhard (1990), Pearls in Graph Theory: A Comprehensive Introduction, Academic Press, pp. 77–81, ISBN 0-12-328552-6 ..
Holton, D. A.; Sheehan, J. (1993), The Petersen Graph, Cambridge University Press, pp. 183-213, ISBN 0-521-43594-3 ..
Lubotzky, A.; Phillips, R.; Sarnak, P. (1988), «Ramanujan graphs», Combinatorica 8 (3): 261-277, MR 963118, doi:10.1007/BF02126799 ..
Tutte, W. T. (1947), «A family of cubical graphs», Proc. Cambridge Philos. Soc. 43 (4): 459-474, doi:10.1017/S0305004100023720 ..

Enlaces externos

Brouwer, Andries E. Cages

Royle, Gordon. Cubic Cages and Higher valency cages

Weisstein, Eric W. «Cage Graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.

Datos: Q841007