Grafos con grupo dado de automorfismos

Authors

  • Héctor Hevia Universidad Católica de Valparaíso.

DOI:

https://doi.org/10.22199/S07160917.1995.0002.00008

Abstract

En un famoso artículo publicado en 1938, Roberto Frucht probó que si ? es un grupo finito dado, entonces existe un grafo cuyo grupo de automorfismos es isomorfo a ?. La publicación de Frucht de 1938 fue seguida por otra en 1949 que, en algún sentido, refinaba su primer resultado. Ambas publicaciones generaron un notable número de artículos sobre temas relacionados, así como una interesante búsqueda de los grafos más pequeños con grupo de automorfismos isomorfo a un cierto grupo dado ?. El propósito de este artículo es hacer una recopilación de las investigaciones realizadas principalmente en esta última dirección.

Dedicado a Roberto Frucht con ocasión de su cumpleaños 89.

Author Biography

Héctor Hevia, Universidad Católica de Valparaíso.

Instituto de Matemáticas.

References

[1] W. Arlinghaus, The structure of minimal graphs with given abelian automorphism group. Ph. D. dissertation, Wayne State University (1979).
[2] W. Arlinghaus, The classification of minimal graphs with given abelian automorphism group. Memoirs Amer. Math. Soc. 57 No. 330 (1985).
[3] L. Babai, On the mínimum order of graphs with given group. Canad. Math. Bull. 17, pp. 467-470 (1974).
[4] L. Babai, On the abstract group of automorphisms. Combinatorics, Cambridge Universíty Press, London, pp. 1-40 (1981).
[5] A. T. Balaban, Valence-isomerism of cyclopolyenes. Rev. Roumaine Chim. 11, pp. 1097-1116 (1966); erratum: 12, pp. 103 (1967).
[6] A. T. Balaban, R. O. Davies, F. Harary, A. Hill y R. Westwick, Cubic identity graphs and planar graphs derived from trees. Austral. Math.Soc. 11, pp. 207-21S (1970).
[7] N. L. Biggs, E. K. Lloyd y R. J. Wilson, Graph Theory 1736-1936.Oxford University Press, London (1976).
[8] l. Z. Bouwer y R. Frucht, Line-minimal graphs with cyclic group. A Survey of Combinatorial Theory (ed. J. N. Srivastava). North Holland, New York, pp. 53-67 (1973).
[9] F. C. Bnssemaker, S. Cobeljic, D. M. Cvetkovic y J. J. Seidel, Computer lnvestigation of Cubic Graphs, T. H. Report 76-WSK-01 Technological University, Eindhoven, Netherlands (1976).
[10] G. Chartrand y L. Lesniak, Graphs and Digraphs, 2nd. Edition. Wadsworth & Brooks/Cole, Monterey (1986)
[11] J. Dávila, R. Giudici y S. Ruiz, Smallest tetravalent graphs with a given cyclic group of automorphisms. Notas de la Sociedad de Matemática de Chile X, pp. 101-109 (1991).
[12] L. Euler, Solutio problematis ad geometriam situs pertinentis. Comment. Academiae Sci. I.Petropolitanae 8, pp. 128-140 (1736).
[13] R. Frucht, Über die Darstellung endlicher Abelscher Gruppen durch Kollineationen. J. Reine Angew. Math. 166, pp. 16-29 (1931).
[14] R. Frucht, Herstellung von Graphen mit vorgegebener abstrakter Gruppe. Compositio Math. 6, pp. 239-250 (1938).
[15] R. Frucht, On the groups of repeated graphs. Bull. Amer. Math. Soc. 55, pp. 418-420 (1949).
[16] R. Frucht, Graphs of degree three with a given abstract group. Canad. J. Math 1, pp. 365-378 (1949).
[17] R. Frucht, How to describe a graph. Ann. N. Y. Acad. Sci. 175, pp. 159-167 (1970).
[18] R. Frucht, A canonical representation of trivalent hamiltonian graphs. J. Graph Theory 1, pp. 45-60 (1977).
[19] R. Frucht, How I became interested in graphs and groups. J. Graph Theory 6, pp. 101-104 (1982).
[20] R. Frucht, A. Gewirtz and L. V. Quintas, El número mínimo de líneas para grafos conexos con grupo de automorfismos de orden 3. Scientia 142, pp. 72-85 (1971).
[21] A. Gewirtz, A. Hill y L. V. Quintas, El número mínimo de puntos para grafos regulares y asimétricos. Scientia 138, pp. 103-111 (1969).
[22] L. Goldschmidt, Linear graphs and groups. Masters' thesis, Brooklyn College, (1956).
[23] D. W. Grace, Computer search for non-isomorphic convex polyhedra. Stanford Computation Center Technical Report CS 15(1956).
[24] F. Harary y E. M. Palmer, The smallest graph whose group is cyclic. Czech. Math. J. 16, pp. 70-71 (1966).
[25] H. Hevia, Sobre el número mínimo de puntos para que un grafo ncíclico exista. Tesis de Magíster, Universidad Técnica Federico Santa María (1976).
[26] H. Hevia, Representación orbital de grafos y número mínimo de puntos para grafos n-cíclicos, n una potencia de primo. Scientia 148, pp. 102-122 (1977).
[27] H. Hevia, Smallest connected cubic graphs with a given cyclic group of automorphisms. Graph Theory, Combinatorics, Algorithms and Applications. (eds. Y. Alavi. F. R. K. Chung, R. L. Graham, and D. F. Hsu) SIAM Publications, Philadelphia, pp. 212-229 (1991).
[28] H. Hevia y S. Ruiz, Smallest trivalent graphs with a given cyclic group of automorphisms. Scientia Series A: Math. Se. 2, pp. 53-73 (1988).
[29] l. N. Kagno, Desargues' and Pappus' graphs and their groups. Amer. J. Math. 69, pp. 859-862 (1947).
[30] V. A. Kohov, All cubic graphs of least arder with a trivial automorphism group. Programmirovanie No. 4, pp. 106-107, 112. (1976) (Ver MR 54# 12565.)
[31] D. Konig, Theorie der endlichen und unendlichen Graphen (Kombinatorische Topologie der Streckenkomplexe). Akademische Verlagsgesellschaft, Leipzig (1936).
[32] L. Lovász, Combinatoria[ Problems and Exercises. North-Holland, New York (1979).
[33] R. L. Meriwether, Smallest graphs with a given cyclic group. (1963) No publicado, ver MR 33 # 2563.
[34] Petrenjuk L. P. y Petrenjuk A. N., On constructive enumeration of 12 vertex cubic graphs. Combinatoria! Analysis 3 Moscow (1974).
[35] L. V. Quintas, Extrema concerning asymmetric graphs. J. Comb. Th. 3, pp. 57-82 (1967).
[36] R. Rambau, Least arder 4-regular DDR identity graphs. Notes from New York Graph Theory Day V (eds. J. W. Kennedy and L. V. Quintas) The New York Academy of Sciences, pp. 22-23 (1982).
[37] G. Sabidussi, Graphs with given group and given graph-theoretical properties. Canad. J. Math. 9, pp. 515-525 (1957).
[38] G. Sabidussi, On the mínimum order of graphs with given automorphism group. Monatsh. Math. 63, pp. 124-127 (1959).

Published

2018-04-03

How to Cite

[1]
H. Hevia, “Grafos con grupo dado de automorfismos”, Proyecciones (Antofagasta, On line), vol. 14, no. 2, pp. 139-167, Apr. 2018.

Issue

Section

Artículos