En el área matemática de la teoría de grafos , una jaula es un grafo regular que tiene la menor cantidad posible de vértices para su circunferencia .
Formalmente, un gráfico ( r , g ) se define como un gráfico 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 jaula ( r , g ) es una gráfica ( r , g ) con el menor número posible de vértices, entre todas las gráficas ( r , g ). Una jaula (3, g ) a menudo se llama jaula g .
Se sabe que existe un gráfico ( r , g ) para cualquier combinación de r ≥ 2 y g ≥ 3. De ello se deduce que existen todas las jaulas ( r , g ).
Si existe una gráfica de Moore con grado ry circunferencia g , debe ser una jaula. Por otra parte, los límites de los tamaños de los gráficos Moore generalizar a jaulas: cualquier jaula con impar circunferencia g debe tener al menos
vértices, y cualquier jaula con incluso la circunferencia g deben tener al menos
vértices. Cualquier gráfico ( r , g ) con exactamente esta cantidad de vértices es, por definición, un gráfico 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 jaulas no isomórficas (3,10), cada una con 70 vértices: la jaula Balaban de 10 , la gráfica de Harries y la gráfica de Harries-Wong . Pero solo hay una jaula ( 3,11): la jaula Balaban de 11 (con 112 vértices).
Jaulas conocidas
Una gráfica 1-regular no tiene ciclo, y una gráfica 2-regular conectada tiene una circunferencia igual a su número de vértices, por lo que las jaulas solo son de interés para r ≥ 3. La ( r , 3) -cage es una gráfica completa K r +1 en r +1 vértices, y la jaula ( r , 4) es un gráfico bipartito completo K r , r en 2 r vértices.
Las jaulas notables incluyen:
- (3,5) -cage: el gráfico de Petersen , 10 vértices
- (3,6) -cage: el gráfico de Heawood , 14 vértices
- (3,8) -cage: el gráfico de Tutte-Coxeter , 30 vértices
- (3,10) -jaula: Balaban 10-jaula , 70 vértices
- (3,11) -jaula: Balaban 11-jaula , 112 vértices
- (4,5) -cage: el gráfico de Robertson , 19 vértices
- (7,5) -cage: El gráfico de Hoffman-Singleton , 50 vértices.
- Cuando r - 1 es una potencia primaria, las jaulas ( r , 6) son las gráficas de incidencia de los planos proyectivos .
- Cuando r - 1 es una potencia prima, las jaulas ( r , 8) y ( r , 12) son polígonos generalizados .
Los números de vértices en las jaulas conocidas ( r , g ), para valores de r > 2 yg > 2, distintos de los planos proyectivos y polígonos generalizados, son:
gramo r | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|
3 | 4 | 6 | 10 | 14 | 24 | 30 | 58 | 70 | 112 | 126 |
4 | 5 | 8 | 19 | 26 | 67 | 80 | 728 | |||
5 | 6 | 10 | 30 | 42 | 170 | 2730 | ||||
6 | 7 | 12 | 40 | 62 | 312 | 7812 | ||||
7 | 8 | 14 | 50 | 90 |
Asintóticos
Para valores grandes de g , la cota de Moore implica que el número n de vértices debe crecer al menos individualmente exponencialmente en función de g . De manera equivalente, g puede ser como mucho proporcional al logaritmo de n . Más precisamente,
Se cree que este límite es estrecho o casi estrecho ( Bollobás & 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 individualmente de forma exponencial pero a una tasa más alta que el límite de Moore). Específicamente, la construcción de gráficos de Ramanujan definidos por Lubotzky, Phillips y Sarnak (1988) satisfacen el límite
Este límite fue mejorado ligeramente por Lazebnik, Ustimenko & 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
- Biggs, Norman (1993), Algebraic Graph Theory (2ª ed.), Cambridge Mathematical Library, págs. 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, doi : 10.1002 / jgt.10023 , MR 1883596.
- Exoo, G; Jajcay, R (2008), "Jaula Dynamic Survey" , encuestas dinámicas, Revista Electrónica de Combinatoria , DS16 , Archivado desde el original en 01/01/2015 , recuperada 2012-03-25.
- Erdős, Paul ; Rényi, Alfréd ; Sós, Vera T. (1966), "Sobre un problema de teoría de grafos" (PDF) , Studia Sci. Matemáticas. Hungar. , 1 : 215-235, Archivado desde el original (PDF) en 09/03/2016 , obtenidos 2010-02-23.
- Hartsfield, Nora ; Ringel, Gerhard (1990), Perlas en teoría de grafos: una introducción comprensiva , Academic Press, págs. 77–81 , ISBN 0-12-328552-6.
- Holton, DA; Sheehan, J. (1993), The Petersen Graph , Cambridge University Press , págs. 183–213, ISBN 0-521-43594-3.
- Lazebnik, F .; Ustimenko, VA; Woldar, AJ (1995), "Una nueva serie de gráficos densos de gran circunferencia", Boletín de la Sociedad Americana de Matemáticas , Nueva serie, 32 (1): 73–79, arXiv : math / 9501231 , doi : 10.1090 / S0273- 0979-1995-00569-0 , MR 1284775.
- Lubotzky, A .; Phillips, R .; Sarnak, P. (1988), "Ramanujan graphs", Combinatorica , 8 (3): 261-277, doi : 10.1007 / BF02126799 , MR 0963118.
- Tutte, WT (1947), "Una familia de gráficos cúbicos", Proc. Cambridge Philos. Soc. , 43 (4): 459–474, Bibcode : 1947PCPS ... 43..459T , doi : 10.1017 / S0305004100023720.
enlaces externos
- Brouwer, Andries E. Cages
- Royle, Gordon. Jaulas cúbicas y jaulas de valencia superior
- Weisstein, Eric W. "Gráfico de jaula" . MathWorld .