Is it known how many graphs on $n$ vertices have the same characteristic equations?

Solution 1:

If the characteristic polynomial of two graphs is the same (with respect to the adjacency matrix), we say that they are cospectral (with respect to the adjacency matrix), because this is equivalent to asking that the eigenvalues are the same.

A graph is determined by spectrum (DS) if it is not cospectral with any other graph. So, you are looking for the number of non-DS graphs on $n$ vertices.

Thee OEIS sequence A099883 gives the values of your function $C(n)$ for $n=1, 2, \dots, 9$, but this appears to be a duplicate of A006608, which goes up to $n=12$.

For more general bounds, see the paper Which graphs are determined by their spectrum? by van Dam and Haemers, and the book Spectra of Graphs by Brouwer and Haemers. We have an asymptotic lower bound on $C(n)$: if $g_n$ is the total number of non-isomorphic graphs on $n$ vertices, then $$ C(n) \ge n^3 g_{n-1}\left( \frac1{24} - o(1)\right). $$ Unfortunately, $g_n$ is much larger than $n^3 g_{n-1}$: asymptotically, $g_n \sim 2^{n(n-1)/2}/n!$. So this doesn't tell us much about what fraction of the $n$-vertex graphs are DS.

Brouwer and Haemers have this to say about upper bounds on $C(n)$:

It seems more likely that almost all graphs are DS, than that almost all graphs are non-DS. Yet much less is known about DS graphs than about non-DS graphs. For example, we do not know of a satisfying counterpart to the lower bounds for non-DS graphs...