The Automorphism Groups of Graphs

Abstract

We have shown that to identify a generating set of the automorphism group of a graph with n vertices, we only need to test the circlical nonseparable basic permutations of Sn that do not consist of a single cycle of order greater than 2, and the nonseparable involutions of Sn. We have also shown that it is possible to determine the automorphism group of certain graphs by investigating the local automorphisms. We have also proved several theorems that could be applicable to the problem of determining the necessary and sufficient conditions that an abstract group be equivalent to the auto,morphism group of some graph. We have by no means exhausted the set of results that could be proved in the directions that this paper has taken. The most fertile areas seem to be the ones investigated in section 5 and Section 6. Neither have we found the most efficient algorithm for determining the automorphism group of a graph. We have made a good start though. The proof of results in graph theory usually entails the investigation of many cases and subcases. Subsequently the results come very slowly and there are many conjectures that seem reasonable but take a long time to discredit. From the point of view of the researcher I would say that theorems 1, 2 and 4 were the key results that allowed me to come up with the others.

Missing page 19.