Grafo distância-transitivo
Grafo distância-transitivo | |
---|---|
![]() |
Famílias de grafos definidos por seus automorfismos | ||||
distância-transitivo | distância-regular | fortemente regular | ||
simétrico (arco-transitivo) | t-transitivo, t ≥ 2 | . | ||
(se conectado) | ||||
transitivo nos vértices e nas arestas | aresta-transitivo e regular | aresta-transitivo | ||
vértice-transitivo | regular | |||
grafo de Cayley | antissimétrico | assimétrico |
No campo da matemática da teoria dos grafos, um grafo distância-transitivo é um grafo tal que, dados dois vértices quaisquer v e w em qualquer distância i, e quaisquer outros dois vértices x e y à mesma distância, há um automorfismo do grafo que carrega v para x e w para y.
Um grafo distância-transitivo é vértice-transitivo e simétrico bem como distância-regular.
Um grafo distância-transitivo é interessante, em parte, porque tem um grande grupo de automorfismo. Alguns exemplos interessantes de grupos finitos são os grupos de automorfismos de grafos distância-transitivos, especialmente daqueles cujo diâmetro é de 2.
Grafos distância-transitivos foram definidos primeiramente em 1971 por Norman L. Biggs e D. H. Smith, que mostraram que existem apenas 12 grafos distância-transitivos trivalentes finitos. São eles:
Nome do grafo | Contagem de vértices | Diâmetro | Cintura | array de interseção |
---|---|---|---|---|
grafo completo K4 | 4 | 1 | 3 | {3;1} |
grafo bipartido completo K3,3 | 6 | 2 | 4 | {3,2;1,3} |
grafo de Petersen | 10 | 2 | 5 | {3,2;1,1} |
grafo do cubo | 8 | 3 | 4 | {3,2,1;1,2,3} |
grafo de Heawood | 14 | 3 | 6 | {3,2,2;1,1,3} |
grafo de Papo | 18 | 4 | 6 | {3,2,2,1;1,1,2,3} |
grafo de Coxeter | 28 | 4 | 7 | {3,2,2,1;1,1,1,2} |
grafo de Tutte–Coxeter | 30 | 4 | 8 | {3,2,2,2;1,1,1,3} |
grafo do dodecaedro | 20 | 5 | 5 | {3,2,1,1,1;1,1,1,2,3} |
grafo de Desargues | 20 | 5 | 6 | {3,2,2,1,1;1,1,2,2,3} |
grafo de Biggs-Smith | 102 | 7 | 9 | {3,2,2,2,1,1,1;1,1,1,1,1,1,3} |
grafo de Foster | 90 | 8 | 10 | {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3} |
Independente em 1969, um grupo de russos liderados por Georgy Adelson-Velsky mostrou que existem grafos que são distância-regulares, mas não distância-transitivos. O único grafo deste tipo com um grau três é o Tutte 12-gaiola de 126 vértices. O menor grafo distância-regular que não é a distância-transitivo é o grafo de Shrikhande. Listas completas de grafos distância-transitivos são conhecidas para alguns graus maiores do que três, mas a classificação de grafos distância-transitivos com graus de vértice arbitrariamente grandes continua em aberto.
A mais simples família de exemplos assintótica de grafos distância-transitivos são os grafos Hipercubo. Outras famílias são os grafos cubo dobrado e os grafos torre quadrados. Todas essas três famílias têm arbitrariamente um grau elevado.
Referências
- Primeiros trabalhos
- Adel'son-Vel'skii, G. M.; Veĭsfeĭler, B. Ju.; Leman, A. A.; Faradžev, I. A. (1969), «An example of a graph which has no transitive group of automorphisms», Doklady Akademii Nauk SSSR, 185: 975–976, MR0244107 .
- Biggs, Norman (1971), «Intersection matrices for linear graphs», Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), London: Academic Press, pp. 15–23, MR0285421 .
- Biggs, Norman (1971), Finite Groups of Automorphisms, London Mathematical Society Lecture Note Series, 6, London & New York: Cambridge University Press, MR0327563 .
- Biggs, N. L.; Smith, D. H. (1971), «On trivalent graphs», Bulletin of the London Mathematical Society, 3: 155–158, doi:10.1112/blms/3.2.155, MR0286693 .
- Smith, D. H. (1971), «Primitive and imprimitive graphs», The Quarterly Journal of Mathematics, Oxford, Second Series, 22: 551–557, doi:10.1093/qmath/22.4.551, MR0327584 .
- Pesquisas
- Biggs, N. L. (1993), «Distance-Transitive Graphs», Algebraic Graph Theory 2nd ed. , Cambridge University Press, pp. 155–163 , chapter 20.
- Van Bon, John (2007), «Finite primitive distance-transitive graphs», European Journal of Combinatorics, 28 (2): 517–532, doi:10.1016/j.ejc.2005.04.014, MR2287450 .
- Brouwer, A. E.; Cohen, A. M.; Neumaier, A. (1989), «Distance-Transitive Graphs», Distance-Regular Graphs, New York: Springer-Verlag, pp. 214–234 , chapter 7.
- Cohen, A. M. Cohen (2004), «Distance-transitive graphs», in: Beineke, L. W.; Wilson, R. J., Topics in Algebraic Graph Theory, Encyclopedia of Mathematics and its Applications, 102, Cambridge University Press, pp. 222–249 .
- Godsil, C.; Royle, G. (2001), «Distance-Transitive Graphs», Algebraic Graph Theory, New York: Springer-Verlag, pp. 66–69 , section 4.5.
- Ivanov, A. A. (1992), «Distance-transitive graphs and their classification», in: Faradžev, I. A.; Ivanov, A. A.; Klin, M.; Woldar, A. J., The Algebraic Theory of Combinatorial Objects, Math. Appl. (Soviet Series), 84, Dordrecht: Kluwer, pp. 283–378, MR1321634 .