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 K4	4	1	3	{3;1}
Grafo bipartito completo K3,3	6	2	4	{3,2;1,3}
Grafo de Petersen	10	2	5	{3,2;1,1}
Grafo del cubo	8	3	4	{3,2,1;1,2,3}
Grafo de Heawood	14	3	6	{3,2,2;1,1,3}
Grafo de Papo	18	4	6	{3,2,2,1;1,1,2,3}
Grafo de Coxeter	28	4	7	{3,2,2,1;1,1,1,2}
Grafo de Tutte-Coxeter	30	4	8	{3,2,2,2;1,1,1,3}
Grafo del dodecaedro	20	5	5	{3,2,1,1,1;1,1,1,2,3}
Grafo de Desargues	20	5	6	{3,2,2,1,1;1,1,2,2,3}
Grafo de Biggs-Smith	102	7	9	{3,2,2,2,1,1,1;1,1,1,1,1,1,3}
Grafo de Foster	90	8	10	{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.