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
$\begingroup$
$\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$– Chris GodsilCommented Jul 1, 2012 at 17:46
-
$\begingroup$ @Chris:Thank you,I will clarify my first question in some days $\endgroup$– XL _At_Here_ThereCommented Jul 2, 2012 at 0:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Jul 1, 2012 at 8:31