Diferencia entre revisiones de «Grafo distancia-transitivo»
Sin resumen de edición |
Sin resumen de edición |
||
| Línea 1: | Línea 1: | ||
[[Image:BiggsSmith.svg|thumb|right|El [[grafo de Biggs-Smith]], el mayor grafo 3-regular distancia-transitivo]] |
[[Image:BiggsSmith.svg|thumb|right|El [[grafo de Biggs-Smith]], el mayor grafo 3-regular distancia-transitivo]] |
||
En el campo [[Matemática|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 (teoría de grafos)|automorfismo]] del grafo que transforma ''v'' en ''x'' y ''w'' en ''y''.<ref name= |
En el campo [[Matemática|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 (teoría de grafos)|automorfismo]] del grafo que transforma ''v'' en ''x'' y ''w'' en ''y''.<ref name=DTG>{{cita libro|título=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|editorial=Springer|año=2011|url=https://books.google.es/books?id=tTaqCAAAQBAJ&pg=PA10#v=onepage&q&f=false|isbn=9783642229350|páginas= 10 de 702|fechaacceso= 07 de septiembre de 2022}}</ref> |
||
Un grafo distancia-transitivo es [[Grafo vértice-transitivo|vértice-transitivo]] y [[Grafo simétrico|simétrico]] así como [[Grafo distancia-regular|distancia-regular]]. |
Un grafo distancia-transitivo es [[Grafo vértice-transitivo|vértice-transitivo]] y [[Grafo simétrico|simétrico]] así como [[Grafo distancia-regular|distancia-regular]].<ref name=AEBAMCAN>{{cita libro|título=Distance-Regular Graphs|autor=Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier|editorial=Springer Science & Business Media|año=2012|url=https://books.google.es/books?id=v6brCAAAQBAJ&printsec=frontcover&dq#v=onepage&q&f=false|isbn=9783642743412|páginas=495|fechaacceso= 07 de septiembre de 2022}}</ref> |
||
El interés en los grafos distancia-transitivos radica en parte en que tienen un [[Automorfismo|grupo de automorfismos]] grande. Algunos [[Grupo finito|grupos finitos]] interesantes son los grupos de automorfismos de grafos distancia-transitivos, especialmente de aquellos cuyo diámetro es 2. |
El interés en los grafos distancia-transitivos radica en parte en que tienen un [[Automorfismo|grupo de automorfismos]] grande. Algunos [[Grupo finito|grupos finitos]] interesantes son los grupos de automorfismos de grafos distancia-transitivos, especialmente de aquellos cuyo diámetro es 2. |
||
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 [[Grafo cúbico|cúbicos]] finitos. Estos son: |
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 [[Grafo cúbico|cúbicos]] finitos. Estos son:<ref name=NBNLBBN>{{cita libro|título=Algebraic Graph Theory|autor=Norman Biggs, Norman Linstead Biggs, Biggs Norman|editorial=Cambridge University Press|año=1993|url=https://books.google.es/books?id=6TasRmIFOxQC&pg=PA171#v=onepage&q&f=false|isbn=9780521458979|páginas= 171 de 205|fechaacceso= 07 de septiembre de 2022}}</ref> |
||
{| class="wikitable" border="1" |
{| class="wikitable" border="1" |
||
|- |
|- |
||
Revisión del 18:00 7 sep 2022
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 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 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.
- ↑ 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.