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.
Primeiros trabalhos .
.
.
.
.
Pesquisas , chapter 20.
.
, chapter 7.
.
, section 4.5.
.
Categoria:Famílias de grafos Categoria:Teoria dos grafos Categoria:Grafos regulares