Estimation of DS graph growth

Question

We know that $DS$ graphs are such connected graphs that determinable by their adjacency spectrum.

Suppose $DS(n)$ and $G(n)$ show the number of $DS$ graphs and all graphs with $n$ vertices,respectively.

$1)$ Do we have any good approximation for $DS(n)$(even if $n$ be sufficiently large)?

$2)$ what is the behavior of $‎\alpha$, if we have:

‎ $lim (DS(n)‎‎/ (G(n)-DS(n))^\alpha=c‎\neq‎0)$

$n ‎\rightarrow‎‎ ‎\infty‎$

Is there any new survey about DS graphs, after 2010?

Haemers conjectures that the proportion of graphs characterized by their spectrum goes to 1 as $n$ increases. And I am wondering how often you expect the topic to be surveyed. — Chris Godsil, Commented Dec 26, 2011 at 15:21
When the time of growing of tulips comes, in every land, tulips will grow."BOLYAI" I designed some problems that are interesting for me and I have some plan for solving them. I searched a lot about them, but I didn't found exact answer. Many of my personal problem, as I see here, worked before. What do you think Dear Godsil? Is it good or bad? Please give me reference about this conjecture. Thanks — Shahrooz, Commented Dec 26, 2011 at 19:09

Brendan McKay · Accepted Answer · 2011-12-26 01:47:53Z

6

As far as I know, the computation of these values up to 11 vertices by van Dam and Haemers is still the best result. No asymptotics are known.

answered Dec 26, 2011 at 1:47

Brendan McKay

37.7k3 gold badges80 silver badges147 bronze badges

$\begingroup$ For us ignoramus, what ARE DS graphs? $\endgroup$
– Igor Rivin
Commented Dec 26, 2011 at 12:02
$\begingroup$ Shahrooz's first line is a definition, even though it doesn't look like one. A graph is DS if it is the only graph whose adjacency matrix has that characteristic polynomial. This is not standard terminology. $\endgroup$
– Brendan McKay
Commented Dec 26, 2011 at 14:24
$\begingroup$ Dear McKay, I found a paper with name "Cospectral graphs on 12 vertices"(A. E. Brouwer, E. Spence). $\endgroup$
– Shahrooz
Commented Dec 26, 2011 at 19:43

Add a comment |

1 Answer 1