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.


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.

  • $\begingroup$ The asymptotic bound you gave holds for any graph with $n$ vertices, without considering it connectedness or number of edges. So connectivity and number of edges do not matter in asymptotic case? $\endgroup$ – DurgaDatta Dec 19 '12 at 10:20
  • $\begingroup$ Yes. You can check the standard textbook on this topic which is "Graphical Enumeration" by Harary and Palmer $\endgroup$ – Jernej Dec 19 '12 at 13:18

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

  • $\begingroup$ I computed the exact worst case complexity of brute force permutation testing if that helps: oeis.org/A186202 $\endgroup$ – Chad Brewbaker Dec 19 '12 at 18:36

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.