Gaiola (teoria dos gráficos) - Cage (graph theory)

Na área matemática da teoria dos grafos , uma gaiola é um gráfico regular que possui o menor número possível de vértices em sua circunferência .

Formalmente, um ( r , g ) -grafo é definido como um grafo no qual cada vértice tem exatamente r vizinhos, e no qual o ciclo mais curto tem comprimento exatamente g . Uma gaiola ( r , g ) é um gráfico ( r , g ) com o menor número possível de vértices, entre todos os gráficos ( r , g ). A (3, g ) -cage é muitas vezes chamado um g -cage.

É sabido que um gráfico ( r , g ) existe para qualquer combinação de r ≥ 2 eg ≥ 3. Segue-se que todas as gaiolas ( r , g ) existem.

Se houver um gráfico de Moore com grau r e circunferência g , ele deve ser uma gaiola. Além disso, os limites dos tamanhos dos gráficos de Moore generalizam para gaiolas: qualquer gaiola com circunferência ímpar g deve ter pelo menos

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

vértices, e qualquer gaiola com girth g deve ter pelo menos

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

vértices. Qualquer gráfico ( r , g ) com exatamente esse número de vértices é, por definição, um gráfico de Moore e, portanto, automaticamente uma gaiola.

Pode haver várias gaiolas para uma determinada combinação de r e g . Por exemplo, existem três gaiolas não isomórficas (3,10), cada uma com 70 vértices: a gaiola de 10 Balaban , o gráfico de Harries e o gráfico de Harries – Wong . Mas há apenas uma (3,11) -gaiola: a Balaban 11-gaiola (com 112 vértices).

Gaiolas conhecidas

Um gráfico 1-regular não tem ciclo e um gráfico 2-regular conectado tem circunferência igual ao seu número de vértices, então as gaiolas são de interesse apenas para r ≥ 3. A gaiola ( r , 3) é um gráfico completo K _{r +1} em r +1 vértices, e a gaiola ( r , 4) é um grafo bipartido completo K _{r , r} em 2 r vértices.

Gaiolas notáveis ​​incluem:

• (3,5) -gaiola: o gráfico de Petersen , 10 vértices
• (3,6) -gaiola: o gráfico de Heawood , 14 vértices
• (3,8) -gaiola: o gráfico de Tutte-Coxeter , 30 vértices
• (3,10) -gaiola: a gaiola Balaban 10 , 70 vértices
• (3,11) -gaiola: o Balaban 11-gaiola , 112 vértices
• (4,5) -gaiola: o gráfico de Robertson , 19 vértices
• (7,5) -gaiola: O gráfico de Hoffman – Singleton , 50 vértices.
• Quando r  - 1 é uma potência primária, as ( r , 6) gaiolas são os gráficos de incidência dos planos projetivos .
• Quando r  - 1 é uma potência primária, as gaiolas ( r , 8) e ( r , 12) são polígonos generalizados .

Os números de vértices nas gaiolas conhecidas ( r , g ), para valores de r > 2 e g > 2, que não sejam planos projetivos e polígonos generalizados, são:

g 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

Assintóticos

Para grandes valores de g , o limite de Moore implica que o número n de vértices deve crescer pelo menos uma vez exponencialmente em função de g . Equivalentemente, g pode ser no máximo proporcional ao logaritmo de n . Mais precisamente,

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

Acredita-se que esse limite seja apertado ou quase apertado ( Bollobás & Szemerédi 2002 ). Os limites inferiores mais conhecidos em g também são logarítmicos, mas com um fator constante menor (implicando que n cresce exponencialmente, mas a uma taxa mais alta do que o limite de Moore). Especificamente, a construção de grafos Ramanujan definidos por Lubotzky, Phillips & Sarnak (1988) satisfazem o limite

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

Este limite foi ligeiramente melhorado por Lazebnik, Ustimenko & Woldar (1995) .

É improvável que esses gráficos sejam gaiolas, mas sua existência fornece um limite superior para o número de vértices necessários em uma gaiola.

Referências

• Biggs, Norman (1993), Algebraic Graph Theory (2ª ed.), 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, doi : 10.1002 / jgt.10023 , MR   1883596 .
• Exoo, G; Jajcay, R (2008), "Dynamic Cage Survey" , Dynamic Surveys, Electronic Journal of Combinatorics , DS16 , arquivado do original em 01/01/2015 , recuperado em 25/03/2012 .
• Erdős, Paul ; Rényi, Alfréd ; Sós, Vera T. (1966), "On a problem of graph theory" (PDF) , Studia Sei. Matemática. Hungar. , 1 : 215–235, arquivado do original (PDF) em 09/03/2016 , recuperado em 23/02/2010 .
• Hartsfield, Nora ; Ringel, Gerhard (1990), Pearls in Graph Theory: A Comprehensive Introduction , Academic Press, pp.  77-81 , ISBN   0-12-328552-6 .
• Holton, DA; Sheehan, J. (1993), The Petersen Graph , Cambridge University Press , pp. 183–213, ISBN   0-521-43594-3 .
• Lazebnik, F .; Ustimenko, VA; Woldar, AJ (1995), "A new series of dense graphs of high girth", Bulletin of the American Mathematical Society , New Series, 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), "A family of cubical graphs", Proc. Cambridge Philos. Soc. , 43 (4): 459-474, bibcode : 1947PCPS ... 43..459T , doi : 10,1017 / S0305004100023720 .

links externos

• Brouwer, Andries E. Cages
• Royle, Gordon. Gaiolas cúbicas e gaiolas de valência superior
• Weisstein, Eric W. "Cage Graph" . MathWorld .