On finding the number of graph automorphisms

This paper investigates the enumerability of the function GA, the number of automorphisms of an undirected graph, in relation to the computational complexity of GI, the Graph Isomorphism problem. A function f (on graphs) is b(n)-enumerable if there exists a function g∈PF such that for all n-node graphs G, g(G) lists b(n) numbers, one of which is f(G). The results in this paper show the following connections between the enumerability of GA and the Graph Isomorphism problem. 1. For ε<½, if GA is n^ε-enumerable then GI∈P. 2. If GA is polynomially enumerable then GI∈R. 3. For all constants c, with c>e≈2.718, GA is cⁿ-enumerable