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]
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
editarLos 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.
Referencias
editar- ↑ 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
editar- 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
editar- Weisstein, Eric W. «Distance-Transitive Graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
Datos: Q4391306
Multimedia: Distance-transitive graphs / Q4391306
