Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
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 Dec 26 '11 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 Dec 26 '11 at 19:09

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
For us ignoramus, what ARE DS graphs? –  Igor Rivin Dec 26 '11 at 12:02
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. –  Brendan McKay Dec 26 '11 at 14:24
Dear McKay, I found a paper with name "Cospectral graphs on 12 vertices"(A. E. Brouwer, E. Spence). –  Shahrooz Dec 26 '11 at 19:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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