Grafo distancia-transitivo

El grafo de Biggs-Smith, el mayor grafo 3-regular 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]

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 K₄	4	1	3	{3;1}
Grafo bipartito completo K_3,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.

Referencias

↑ 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.
↑ 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.
↑ 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 Se sugiere usar |número-editores= (ayuda)..