En el campo matemático de la teoría de grafos , un grafo transitivo en función de la distancia es un grafo tal que, dados dos vértices cualesquiera v y w a cualquier distancia i , y cualesquiera otros dos vértices x e y a la misma distancia, existe un automorfismo del grafo que lleva v a x y w a y . Los grafos transitivos en función de la distancia fueron definidos por primera vez en 1971 por Norman L. Biggs y DH Smith.
Un grafo transitivo en función de la distancia es interesante en parte porque tiene un gran grupo de automorfismos . Algunos grupos finitos interesantes son los grupos de automorfismos de grafos transitivos en función de la distancia, especialmente aquellos cuyo diámetro es 2.
Ejemplos
Algunos primeros ejemplos de familias de gráficos transitivos de distancia incluyen:
Clasificación de grafos cúbicos transitivos de distancia
Después de introducirlos en 1971, Biggs y Smith demostraron que sólo hay 12 grafos trivalentes transitivos de distancia conexos y finitos. Estos son:
Relación con los gráficos regulares de distancia
Todo gráfico transitivo en términos de distancia es regular en términos de distancia , pero lo inverso no es necesariamente cierto.
En 1969, antes de la publicación de la definición de Biggs-Smith, un grupo ruso dirigido por Georgy Adelson-Velsky demostró que existen grafos que son regulares en cuanto a la distancia pero no transitivos en cuanto a la distancia. El grafo regular en cuanto a la distancia más pequeño que no es transitivo en cuanto a la distancia es el grafo de Shrikhande , con 16 vértices y grado 6. El único grafo de este tipo con grado tres es el grafo de 12 jaulas de Tutte de 126 vértices . Se conocen listas completas de grafos transitivos en cuanto a la distancia para algunos grados mayores que tres, pero la clasificación de grafos transitivos en cuanto a la distancia con un grado de vértice arbitrariamente grande sigue abierta.
Biggs, Norman (1971), "Matrices de intersección para gráficos lineales", Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) , Londres: Academic Press, págs. 15-23, MR 0285421.
Biggs, Norman (1971), Grupos finitos de automorfismos , London Mathematical Society Lecture Note Series, vol. 6, Londres y Nueva York: Cambridge University Press, MR 0327563.
Biggs, NL; Smith, DH (1971), "Sobre grafos trivalentes", Boletín de la Sociedad Matemática de Londres , 3 (2): 155–158, doi :10.1112/blms/3.2.155, MR 0286693.
Smith, DH (1971), "Gráficos primitivos e imprimitivos", The Quarterly Journal of Mathematics , Segunda serie, 22 (4): 551–557, doi :10.1093/qmath/22.4.551, MR 0327584.
Encuestas
Biggs, NL (1993), "Gráficos transitivos de distancia", Teoría de grafos algebraicos (2.ª ed.), Cambridge University Press, págs. 155-163, capítulo 20.
Van Bon, John (2007), "Gráficos transitivos de distancia primitivos finitos", 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), "Gráficos transitivos de distancia", Distance-Regular Graphs , Nueva York: Springer-Verlag, págs. 214-234, capítulo 7.
Cohen, AM Cohen (2004), "Gráficos transitivos de distancia", en Beineke, LW; Wilson, RJ (eds.), Temas de teoría de grafos algebraicos , Enciclopedia de matemáticas y sus aplicaciones, vol. 102, Cambridge University Press, págs. 222–249.
Godsil, C. ; Royle, G. (2001), "Gráficos transitivos de distancia", Teoría de grafos algebraicos , Nueva York: Springer-Verlag, págs. 66–69, sección 4.5.
Ivanov, AA (1992), "Gráficos transitivos de distancia y su clasificación", en Faradžev, IA; Ivanov, AA; Klin, M.; et al. (eds.), La teoría algebraica de objetos combinatorios , Math. Appl. (Soviet Series), vol. 84, Dordrecht: Kluwer, págs. 283–378, MR 1321634.
