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

1 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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