En el campo matemático de la teoría de grafos, un grafo distancia-transitivo es un grafo tal que, dados dos vértices cualesquiera v y w a cualquier distancia i, y otros dos vértices cualesquiera x y y a la misma distancia, existe un automorfismo del grafo que transforma v en x y w en y.[1]
Un grafo distancia-transitivo es vértice-transitivo y simétrico así como distancia-regular.[2]
El interés en los grafos distancia-transitivos radica en parte en que tienen un grupo de automorfismos grande. Algunos grupos finitos interesantes son los grupos de automorfismos de grafos distancia-transitivos, especialmente de aquellos cuyo diámetro es 2.
Los grafos distancia-transitivos fueron definidos por primera vez en 1971 por Norman L. Biggs y D. H. Smith, quienes demostraron que sólo hay 12 grafos distancia-transitivos cúbicos finitos. Estos son:[3]
Independientemente, un grupo ruso liderado por Georgy Adelson-Velsky demostró en 1969 que existían grafos que son distancia-regulares pero no distancia-transitivos. El único grafo de este tipo de grado tres es la 12-jaula de Tutte de 126 vértices. El menor grafo distancia-regular que no es distancia-transitivo es el grafo de Shrikhande. Se conocen listas completas de grafos distancia-transitivos para algunos grados mayores que tres, pero la clasificación de grafos distancia-transitivos de grados arbitrariamente grandes continúa abierta.
La familia asintótica más simple de ejemplos de grafos transitivos de distancia son los grafos hipercúbicos. Otras familias son los grafos cúbicos plegados y los grafos de torre cuadrados. Las tres familias tienen un grado arbitrariamente alto.
↑Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier (2012). Distance-Regular Graphs. Springer Science & Business Media. p. 495. ISBN9783642743412. Consultado el 7 de septiembre de 2022.
↑Norman Biggs, Norman Linstead Biggs, Biggs Norman (1993). Algebraic Graph Theory. Cambridge University Press. pp. 171 de 205. ISBN9780521458979. Consultado el 7 de septiembre de 2022.
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 SSSR185: 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 Society3 (2): 155-158, MR0286693, doi:10.1112/blms/3.2.155..
Smith, D. H. (1971), «Primitive and imprimitive graphs», The Quarterly Journal of Mathematics. Oxford. Second Series22 (4): 551-557, MR0327584, doi:10.1093/qmath/22.4.551..
Relaciones de datos
Biggs, N. L. (1993), «Distance-Transitive Graphs», Algebraic Graph Theory (2nd edición), Cambridge University Press, pp. 155-163., chapter 20.
Van Bon, John (2007), «Finite primitive distance-transitive graphs», European Journal of Combinatorics28 (2): 517-532, MR2287450, doi:10.1016/j.ejc.2005.04.014..
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», en Beineke, L. W.; Wilson, R. J., 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., section 4.5.
Ivanov, A. A. (1992), «Distance-transitive graphs and their classification», en Faradžev, I. A.; Ivanov, A. A.; Klin, M. et al., eds., The Algebraic Theory of Combinatorial Objects, Math. Appl. (Soviet Series) 84, Dordrecht: Kluwer, pp. 283-378, MR1321634Se sugiere usar |número-editores= (ayuda)..