Grafo distancia-transitivo

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]

El grafo de Biggs-Smith, el mayor grafo 3-regular distancia-transitivo

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 12 grafos distancia-transitivos

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]

Nombre Vértices Diámetro Cintura Matriz de intersección
Grafo completo K4413{3;1}
Grafo bipartito completo K3,3624{3,2;1,3}
Grafo de Petersen1025{3,2;1,1}
Grafo del cubo834{3,2,1;1,2,3}
Grafo de Heawood1436{3,2,2;1,1,3}
Grafo de Papo1846{3,2,2,1;1,1,2,3}
Grafo de Coxeter2847{3,2,2,1;1,1,1,2}
Grafo de Tutte-Coxeter3048{3,2,2,2;1,1,1,3}
Grafo del dodecaedro2055{3,2,1,1,1;1,1,1,2,3}
Grafo de Desargues2056{3,2,2,1,1;1,1,2,2,3}
Grafo de Biggs-Smith10279{3,2,2,2,1,1,1;1,1,1,1,1,1,3}
Grafo de Foster90810{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,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.

Referencias
  1. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011, Proceedings. Springer. 2011. pp. 10 de 702. ISBN 9783642229350. Consultado el 7 de septiembre de 2022.
  2. Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier (2012). Distance-Regular Graphs. Springer Science & Business Media. p. 495. ISBN 9783642743412. Consultado el 7 de septiembre de 2022.
  3. Norman Biggs, Norman Linstead Biggs, Biggs Norman (1993). Algebraic Graph Theory. Cambridge University Press. pp. 171 de 205. ISBN 9780521458979. Consultado el 7 de septiembre de 2022.

Bibliografía
Trabajos iniciales
  • 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, 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, London & New York: Cambridge University Press, MR 0327563..
  • Biggs, N. L.; Smith, D. H. (1971), «On trivalent graphs», Bulletin of the London Mathematical Society 3 (2): 155-158, MR 0286693, doi:10.1112/blms/3.2.155..
  • Smith, D. H. (1971), «Primitive and imprimitive graphs», The Quarterly Journal of Mathematics. Oxford. Second Series 22 (4): 551-557, MR 0327584, 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 Combinatorics 28 (2): 517-532, MR 2287450, 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, MR 1321634 ..

Enlaces externos
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.