1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Chris Godsil Jul 1 '12 at 17:46
  • $\begingroup$ @Chris:Thank you,I will clarify my first question in some days $\endgroup$ – XL _At_Here_There Jul 2 '12 at 0:29
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.