Optimal upper bound on the number of non-isomorphic graphs with certain parameter

Question

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.

Answer 1

This is just a partial answer mainly answering just $a)$ and $b)$

1. The number of non-isomorphic graphs is asymptotically equivalent to $$\frac{2^{n \choose 2}}{n!}$$ Almost all graphs are connected (in fact $k$-connected for any constant $k$) hence this answer your first question.
2. This is an open problem. If we restrict ourselves to trees then it is well known that almost all trees are cospectral hence that for every tree $T$ there exist another non-isomorphic tree $T'$ with equal adjacency spectrum. I believe there is no other result generalizing this one. There is plenty of literature on this subject, check on Google for "cospectral graphs".

It is conjectured that almost all graphs are determined by their spectrum but no real evidence for this fact is known. The conjecture is of course motivated by the isomorphism problem.

The number (and proportion) of cospectral graphs on $n=12$ vertices has been computed recently and can be found here.

Answer 2

Tree isomorphism is polynomial time. Reed, Ronald C. (1972). "The Coding of Various Kinds of Unlabeled Trees". Graph Theory and Computing: 153–182