×

Automorphism groups, isomorphism, reconstruction. (English) Zbl 0846.05042

Graham, R. L. (ed.) et al., Handbook of combinatorics. Vol. 1-2. Amsterdam: Elsevier (North-Holland). 1447-1540 (1995).
The author illustrates the variety of ways in which groups and graphs interact. The treatment to the subject is mostly kept on an elementary level, requiring little more than basic group theory. The effect of powerful results of group theory is already evident in the introductory section. Consequences of the classification of finite simple groups are required for results concerning the representation problem, graph isomorphisms and the reconstruction problem. Strong links to model theory and to the theory of algorithms are demonstrated. Some of the sources of motivation include algebraic topology, differential geometry and even quantum mechanics. The present paper gives an informative survey on results in the following fields: Cayley graphs and vertex-transitive graphs, The representation problem, High symmetry, Graph isomorphism, The reconstruction problem.
For the entire collection see [Zbl 0833.05001].

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite