Saltar para o conteúdo

Grafo distância-transitivo

Origem: Wikipédia, a enciclopédia livre.
Grafo distância-transitivo
Famílias de grafos definidos por seus automorfismos
distância-transitivodistância-regularfortemente regular
simétrico (arco-transitivo)t-transitivo, t ≥ 2.

(se conectado)
transitivo nos vértices e nas arestasaresta-transitivo e regulararesta-transitivo
vértice-transitivoregular
grafo de Cayleyantissimétricoassimé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
  • 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 .
  • 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.
  • 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 .