NOTA: El artículo original es un texto “Microsoft Word” que no se reproduce completamente al usar el navegador “Explorer”. Hay varias omisiones en los símbolos de la equación larga que aparece más abajo y en las 3 líneas anteriores. Al usar los navegadores “Firefox”, “Netscape” o “Safari” hay muchos más errores. Si el lector desea ver el texto original por favor solicítelo de nuestro portal.
Journal of Graph Theory, Vol. 6 (1982) 97-99
® 1982 by John Wiley & Sons, Inc. CCC 0364-9024/82/020097-03$01.30
Roberto Frucht
THE
ANN ARBOR, MI 48109
En el primer libro jamás escrito acerca de la teoría de grafos, Dénes König [8, p.5] definió el grupo (abstracto) de un grafo dado y preguntó en 1936, "¿Cuándo puede considerarse un grupo abstracto dado como el grupo de un grafo y -- si éste fuese el caso -- cómo puede construirse el grafo correspondiente?" ["Wann kann eine gegebene abstrakte Gruppe als die Gruppe eines Graphen aufgefasst werden und—ist dies der Fall—wie kann dann der entsprechende Graph konstruiert werden?"] Roberto Frucht [4] casi inmediatemente dió una respuesta afirmativa a esta pregunta en 1938, cuando presentó una prueba constructiva que para cualquier grupo abstracto finito A, existe un grafo G cuyo grupo automorfismo (permutación) G(G) es isomórfo con A. Tanto este teorema como su demostración usando el gráfico Cayley del grupo se han convertido en una demostración clásica y constituyen la base de la interacción entre grafos y grupos. Todos los teóricos de grafos reconocen éste como un importante resultado pionero.
Muchos artículos subsiguientes, incluyendo algunos por Frucht mismo, han debilitado la hipótesis al probar que muchas y variadas propiedades de un grafo G con G(G) isomórfico a un grupo abstracto A dado pueden especificarse. Ciertamente el descubrimiento de mayor alcance se debe a Babai [2], quien usó un enfoque teórico de categoría (category-theoretic). Un caso muy especial de su resultado más general demuestra que para cualesquiera dos grupos abstractos A y B, existe un grafo G que tiene un arco e tal que G(G) @ A y G(G – e) @ B!
Otra dirección en la cual el teorema de Frucht estimuló resultados importantes involucra la determinación, dado A, del número de a(A) que es el menor número de puntos en un grafo G tal que G(G) @ . El resultado más reciente y definitivo es el de Arlinghaus [1], quien derivó a(A) para cualquier grupo Abeliano A. Este también resumió todos los resultados conocidos obteniendo a(A) para otros grupos A. La invariante relacionada b(A), el número mínimo de puntos en un digrafo D tal que G(D) @ , no ha sido estudiado mucho. Ni siquiera se sabe para cuál A se da b(A) = a(A).
Una tercera dirección de investigación muy importante que ha salido del trabajo original de Frucht involucra la aplicación de grafos y grupos a la incrustación de grafos en superficies, que hasta ha producido el concepto del género de un grupo. La monografía de White [10] es la obra definitiva acerca de este tópico.
He tenido el placer personal de escribir dos artículos con Roberto Frucht. En el primero de éstos [5], propusimos una alternativa a mi operación binaria G1[G2] sobre dos grafos [7], que inicialmente se llamó su composición, pero ahora se conoce también como el producto lexicográfico o corona. Nuestra nueva operación G1 ° G2 fue llamada "corona" por Roberto, por dos razones: (1) porque el grafo resultante a menudo se ve como una corona, (2) "corona" en español se traduce como "crown" o "wreath" en inglés.
Nuestro segundo artículo [6] extendió las formulas de Read [9] para el número de grafos y digrafos complementarios. Nos dimos cuenta que la fórmula de Read se puede generalizar fácilmente afirmando que el número de órbitas auto-complementarias de un grupo de permutación se puede expresar como una suma alternante. Para ilustrar ésto, si
el número de grafos auto-complementarios con p puntos, entonces
En Julio de 1970 visité a Roberto Frucht en Valparaíso, Chile, y conocí a su Mercedes (su esposa, no su auto, como le gustaba bromear). Allí tuve una maravillosa experiencia en evolución lingüística dinámica. Generalmente, Roberto y Mercedes conversan en una mezcolanza de castellano, italiano, francés y alemán. Debido a mi presencia, agregaron inglés a la lista ese día. Ninguno de nosotros sabía en qué idioma saldría la próxima palabra, pero los tres entendimos todo. Una experiencia alucinante pero encantadora.
De acuerdo con la definición del legendario Paul Erdös, un matemático es una persona que activamente hace investigación creativa en matemáticas, y preferiblemente incluso ha descubierto un nuevo teorema durante la semana. Hasta bajo esta rigurosa condición, Roberto Frucht es un matemático hoy en día como lo demuestra su reciente libro [3] (un grafo cero-simétrico es cúbico y punto simétrico pero no simétrico de línea). En su lengua adoptiva, ofrezco un brindis en el cual todos
participamos:
A mi amigo Roberto Frucht: ¡SALUD!
REFERENCIAS
[1] W. Arlinghaus, Smallest graphs with given Abelian group. Ph.D. Thesis, Wayne
[2] L. Babai, Ph.D. Thesis, Eötvös Loránd Tudományegyetem (1976).
[3] H.S.M. Coxeter, R. Frucht, and D.L. Powers, Zero-Symmetric Graphs.
Academic, New York (1981).
[4] R. Frucht, Herstellung von Graphen mit vorgegebener abstrakten Gruppe.
Compositio Math. 6 (1938) 239-250.
[5] R. Frucht and F. Harary, On the corona of two graphs. Aequationes Math.
4 (1970) 322-325.
[6] R. Frucht and F. Harary, Self-complementary generalized orbits of a
permutation group. Canad. Math, Bull. 17 (1974) 203-208.
[7] F. Harary, On the group of the composition of two graphs. Duke Math. J.
26 (1959) 29-34.
[8] D. König, Theorie der endlichen und unendlichen Graphen, Leipzig (1936);
reprinted
[9] R.C. Read, On the number of self-complementary graphs and digraphs.
J. London Math. Soc, 38 (1963) 99-104.
[10] A.T. White, Graphs, Groups and Surfaces, Ameri