Gráfico de distância transitiva - Distance-transitive graph

O gráfico de Biggs-Smith , o maior gráfico transitivo de distância 3 regular.
Faça um gráfico de famílias definidas por seus automorfismos
distância transitiva → distância regular ← fortemente regular
↓
simétrico (arco transitivo) ← t- transitivo, t  ≥ 2 enviesado
↓
(se conectado)
transitivo de vértice e borda 		→ borda transitiva e regular → borda transitiva
↓ ↓ ↓
transitivo de vértice → regular → (se bipartido)
biregular
↑
Gráfico Cayley ← zero-simétrico assimétrico

No matemático campo da teoria gráfico , um diagrama das distâncias e transitória é um gráfico de tal modo que, tendo em conta quaisquer dois vértices de v e w , a qualquer distância i , e quaisquer outros dois vértices x e y no mesmo raio, existe uma automorphism do gráfico que carrega v a x e w a  y . Os gráficos de distância transitiva foram definidos pela primeira vez em 1971 por Norman L. Biggs e DH Smith.

Um gráfico de distância transitiva é interessante em parte porque tem um grande grupo de automorfismo . Alguns grupos finitos interessantes são os grupos de automorfismo de gráficos transitivos por distância, especialmente aqueles cujo diâmetro é 2.

Exemplos

Alguns primeiros exemplos de famílias de gráficos transitivos de distância incluem:

Classificação de gráficos transitivos de distância cúbica

Depois de introduzi-los em 1971, Biggs e Smith mostraram que existem apenas 12 gráficos trivalentes transitivos de distância finitos. Estes são:

Nome do gráfico Contagem de vértices Diâmetro Cilha Matriz de interseção
Gráfico tetraédrico ou gráfico completo K 4 4 1 3 {3; 1}
grafo bipartido completo K 3,3 6 2 4 {3,2; 1,3}
Gráfico de Petersen 10 2 5 {3,2; 1,1}
Gráfico cúbico 8 3 4 {3,2,1; 1,2,3}
Gráfico de Heawood 14 3 6 {3,2,2; 1,1,3}
Gráfico de Pappus 18 4 6 {3,2,2,1; 1,1,2,3}
Gráfico de Coxeter 28 4 7 {3,2,2,1; 1,1,1,2}
Gráfico Tutte-Coxeter 30 4 8 {3,2,2,2; 1,1,1,3}
Gráfico dodecaédrico 20 5 5 {3,2,1,1,1; 1,1,1,2,3}
Gráfico Desargues 20 5 6 {3,2,2,1,1; 1,1,2,2,3}
Gráfico Biggs-Smith 102 7 9 {3,2,2,2,1,1,1,1; 1,1,1,1,1,1,3}
Gráfico Foster 90 8 10 {3,2,2,2,2,1,1,1; 1,1,1,1,2,2,2,3}

Relação com gráficos regulares de distância

Todo gráfico de distância transitiva é distância regular , mas o inverso não é necessariamente verdadeiro.

Em 1969, antes da publicação da definição de Biggs-Smith, um grupo russo liderado por Georgy Adelson-Velsky mostrou que existem gráficos com distância regular, mas não distância transitiva. O único gráfico desse tipo com grau três é a gaiola de 12 Tutte de 126 vértices . O menor gráfico de distância regular que não é transitivo de distância é o gráfico de Shrikhande . Listas completas de grafos transitivos de distância são conhecidas por alguns graus maiores que três, mas a classificação de grafos transitivos de distância com grau de vértice arbitrariamente grande permanece aberta.

Referências

Trabalhos iniciais
  • Adel'son-Vel'skii, GM ; Veĭsfeĭler, B. Ju. ; Leman, AA; Faradžev, IA (1969), "Um exemplo de um gráfico que não tem nenhum grupo transitivo de automorfismos", Doklady Akademii Nauk SSSR , 185 : 975–976, MR  0244107.
  • Biggs, Norman (1971), "Intersection matrices for linear graphs", Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) , London: Academic Press, pp. 15-23, MR  0285421.
  • Biggs, Norman (1971), Finite Groups of Automorphisms , London Mathematical Society Lecture Note Series, 6 , Londres e Nova York: Cambridge University Press, MR  0327563.
  • Biggs, NL; Smith, DH (1971), "On trivalent graphs", Bulletin of the London Mathematical Society , 3 (2): 155–158, doi : 10.1112 / blms / 3.2.155 , MR  0286693.
  • Smith, DH (1971), "Primitive and imprimitive graphs", The Quarterly Journal of Mathematics , Second Series, 22 (4): 551–557, doi : 10.1093 / qmath / 22.4.551 , MR  0327584.
pesquisas
  • Biggs, NL (1993), "Distance-Transitive Graphs", Algebraic Graph Theory (2ª ed.), Cambridge University Press, pp. 155-163, capítulo 20.
  • Van Bon, John (2007), "Finite primitive distance-transit graphs", European Journal of Combinatorics , 28 (2): 517-532, doi : 10.1016 / j.ejc.2005.04.014 , MR  2287450.
  • Brouwer, AE ; Cohen, AM; Neumaier, A. (1989), "Distance-Transitive Graphs", Distance-Regular Graphs , New York: Springer-Verlag, pp. 214-234, Capítulo 7.
  • Cohen, AM Cohen (2004), "Distance-transititive graphs", em Beineke, LW; Wilson, RJ (eds.), 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, seção 4.5.
  • Ivanov, AA (1992), "Distance-transititive graphs and theirclassification", in Faradžev, IA; Ivanov, AA; Klin, M .; et al. (eds.), The Algebraic Theory of Combinatorial Objects , Math. Appl. (Soviética Series), 84 , Dordrecht: Kluwer, pp. 283-378, MR  1321634.

links externos