En el campo matemático de la teoría de grafos , una gráfica de distancia transitiva es una gráfica tal que, dados dos vértices cualesquiera v y w a cualquier distancia i , y otros dos vértices cualesquiera x e y a la misma distancia, existe un automorfismo de la gráfica que lleva v a x y w a y . Los gráficos transitivos de distancia fueron definidos por primera vez en 1971 por Norman L. Biggs y DH Smith.
Un gráfico transitivo de distancia es interesante en parte porque tiene un gran grupo de automorfismos . Algunos grupos finitos interesantes son los grupos de automorfismos de gráficos transitivos de distancia, especialmente de aquellos cuyo diámetro es 2.
Ejemplos
Algunos primeros ejemplos de familias de gráficos transitivos de distancia incluyen:
Clasificación de gráficos cúbicos de distancia transitiva.
Después de introducirlos en 1971, Biggs y Smith demostraron que sólo hay 12 gráficos trivalentes transitivos de distancia conectados finitos. Estos son:
Relación con gráficos de distancia regular
Todo gráfico transitivo de distancia es regular en distancia , pero lo contrario no es necesariamente cierto.
En 1969, antes de la publicación de la definición de Biggs-Smith, un grupo ruso liderado por Georgy Adelson-Velsky demostró que existen gráficos que son regulares en distancia pero no transitivos en distancia. El gráfico de distancia regular más pequeño que no es transitivo en distancia es el gráfico de Shrikhande , con 16 vértices y grado 6. El único gráfico de este tipo con grado tres es el Tutte de 12 jaulas de 126 vértices . Se conocen listas completas de gráficos de distancia transitiva para algunos grados mayores que tres, pero la clasificación de gráficos de distancia transitiva con un grado de vértice arbitrariamente grande permanece abierta.
Biggs, Norman (1971), "Matrices de intersección para gráficos lineales", Matemáticas combinatorias y sus aplicaciones (Proc. Conf., Oxford, 1969) , Londres: Academic Press, págs. 15-23, MR 0285421.
Biggs, Norman (1971), Grupos finitos de automorfismos , Serie de notas de conferencias de la London Mathematical Society, vol. 6, Londres y Nueva York: Cambridge University Press, MR 0327563.
Biggs, Países Bajos; Smith, DH (1971), "Sobre gráficos trivalentes", Boletín de la Sociedad Matemática de Londres , 3 (2): 155–158, doi :10.1112/blms/3.2.155, SEÑOR 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., 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 , SEÑOR 2287450.
Brouwer, AE ; Cohen, AM; Neumaier, A. (1989), "Gráficos transitivos de distancia", Gráficos regulares de distancia , Nueva York: Springer-Verlag, págs., 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., 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 , Matemáticas. Aplica. (Serie soviética), vol. 84, Dordrecht: Kluwer, págs. 283–378, SEÑOR 1321634.
