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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Chris Godsil Dec 26 '11 at 15:21
  • $\begingroup$ 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 $\endgroup$ – Shahrooz Janbaz Dec 26 '11 at 19:09

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.

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

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.