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

CC BY-SA 3.0
2012-12-19T18:36:31.710Z
I computed the exact worst case complexity of brute force permutation testing if that helps: http://oeis.org/A186202
Chad Brewbaker
CC BY-SA 3.0
2012-12-19T18:34:14.577Z
2012-12-19T18:34:14.577Z
Chad Brewbaker
<p>This is just a partial answer mainly answering just $a)$ and $b)$</p>

<ol>
<li>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.</li>
<li>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". </li>
</ol>

<p>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. </p>

<p>The number (and proportion) of cospectral graphs on $n=12$ vertices has been computed recently and can be found <a href="http://www.win.tue.nl/~aeb/preprints/cospectral12.pdf" rel="nofollow">here</a>. </p>

CC BY-SA 3.0
2012-12-19T10:20:16.260Z
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?
DurgaDatta
CC BY-SA 3.0
2012-12-19T13:18:35.260Z
Yes. You can check the standard textbook on this topic which is "Graphical Enumeration" by Harary and Palmer
Jernej
CC BY-SA 3.0
2012-12-19T09:34:20.653Z
2012-12-19T09:34:20.653Z
Jernej
<p>What are the optimal (or best known) bounds (preferably exact or else asymptotic <strong>but not expectation on random graphs</strong>) on the number of  non-isomorphic (unlabelled) simple (no self-loop), undirected graphs with the following parameters/conditions: </p>

<p>a) connected, $|V| = m, \ |E| = n$,<br>
b) (a) AND spectrum of adjacency matrices is same,<br>
c) (a) AND same degree distribution<br>
d) (c) and (b) (i.e. all of the above)</p>

<p>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 <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.4863" rel="nofollow">Cai, Furer and Immerman</a>. 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.</p>

<reference-request><graph-theory><graph-algorithms><graph-isomorphism><spectral-graph-theory>
Optimal upper bound on the number of non-isomorphic graphs with certain parameter
DurgaDatta
# Optimal upper bound on the number of non-isomorphic graphs with certain parameter

(Asked by: username_0 on 2012-12-19)

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.4863). 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.

**Tags:** reference-request, graph-theory, graph-algorithms, graph-isomorphism, spectral-graph-theory

---

## 2 answers

### Answer by username_1 on 2012-12-19. Score: 1

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

> **Comments:**
> **username_1**: I computed the exact worst case complexity of brute force permutation testing if that helps: http://oeis.org/A186202  

---

### Answer by username_2 on 2012-12-19. Score: 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](http://www.win.tue.nl/~aeb/preprints/cospectral12.pdf).

> **Comments:**
> **username_0**: 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?  
> **username_2**: Yes. You can check the standard textbook on this topic which is "Graphical Enumeration" by Harary and Palmer  

---

