1

In what probability does cospectra of adjacent matrix of Cayley graph imply isomorphism of the corresponding group? Further more,In what probability does cospectra of adjacent matrix imply isomorphism of the corresponding graphs

flag
The first question needs to be formulated more carefully. There are graphs which are simultaneously Cayley graphs for two different groups (e.g. the cube is Cayley for $\mathbb{Z}_2^3$ and for $\mathbb{Z}_2\times\mathbb{Z}_4$). But. however you formulate the answer will be that nobody knows. – Chris Godsil Jul 1 at 17:46
@Chris:Thank you,I will clarify my first question in some days – XL Jul 2 at 0:29

1 Answer

2

For your second question, if by probability you mean $$\lim_{n \to \infty} \frac{|S_n|}{|G_n|},$$ where $S_n$ is the set of all possible spectra of simple $n$-vertex graphs, and $G_n$ is the set of isomorphism classes of simple $n$-vertex graphs, then it is conjectured that the above probability is 1. That is, almost all graphs are determined by their spectrum.

See my answer to this question for more information and references.

link|flag

Your Answer

Get an OpenID
or

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