2

show that any directed cycle graph $C_n$ will be uniquely determined by its spectrum of adjacency matrix for directed graph.

it is easy to see that the eigenvalues for directed cycle is $e^{\frac{2\pi ri}{n}} $for $0\leq r\leq n-1$ .

now suppose we have directed graph which its spectrum is what we define above,and we suppose that it is not directed cycle,now I have problem to make contradiction, it will be great if you give me hint,Idea or reference to study ,thanks.

kpax
  • 2,911
  • Your interpretation of the problem is stronger than mine was (on first reading). Namely I thought the problem was merely to show among directed cyclic graphs, $C_n$ can be picked out from knowing the eigenvalues of its adjacency matrix (for a directed graph), while you understand the task to be showing that no other directed graph has the same spectrum. But I suspect that cannot be shown. Consider a directed graph consisting of two copies of $C_n$. Its adjacency matrix would have the same spectrum (albeit with multiplicities doubled). – hardmath Nov 17 '14 at 13:40
  • 1
    The easiest approach would be to use the Perron-Frobenius theory. – Chris Godsil Nov 17 '14 at 17:53
  • @ Chris Godsil ,can you a little explain to me how should I use it? – kpax Nov 17 '14 at 18:55
  • 3
    You know that the spectral radius is 1 and that $A^n=I$. The Perron-Frobenius theory tells you that if there are exactly $k$ eigenvalues with absolute value 1, then the graphs has a $k$-cyclic structure. The wikipedia page is pretty good. – Chris Godsil Nov 17 '14 at 21:30

0 Answers0