What are the optimal (or best known) bounds (preferably exact or else asymptotic but not expectation on random graphs) on the number of non-isomorphic (unlabelled) simple (no self-loop), undirected graphs with the following parameters/conditions:
a) connected, $|V| = m, \ |E| = n$,
b) (a) AND spectrum of adjacency matrices is same,
c) (a) AND same degree distribution
d) (c) and (b) (i.e. all of the above)
My interest is in finding lower bounds on the resource (time steps, variables required etc, enegy.) for solving graph isomorphism problem. I am aware of one such work by Cai, Furer and Immerman. Any other references aiming at or helpful in understanding the optimal resources (in any form) required for solving graph isomorphism problem will be greatly appreciated.