Welcome to MathOverflow

Question

3

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?

flag	asked Dec 25 2011 at 22:49 Shahrooz 972●1●2●13

1

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 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 Dec 26 2011 at 19:09

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

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
9,179●1●15●34

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

Estimation of DS graph growth

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.