6
$\begingroup$

This is related to the following question from cs theory stack exchange: https://cstheory.stackexchange.com/questions/3742/reverse-graph-spectra-problem

So it seems as if given a sequence of real numbers, it is not always possible to generate a 0-1 symmetric matrix (with zeros on the diagonal) whose spectrum is the given sequence. This is because not only is it true that not all sequences can occur as eigenvalues of such matrices, but also because there exist non-isomorphic graphs with the spectrum. This leads to the question of characterizing n-sequences for which such a reverse reconstruction exists and whether such a reverse reconstruction is possible in more specific cases.

Consider the case of simple digraphs (directed graph) and their line digraphs. In this case, the adjacency matrices are again 0-1 matrices with zeroes on the diagonal, but not the matrix need not be symmetric. The following paper shows a clean relationship between the spectrum of a digraph and that of its line digraph: http://www.academia.edu/1462821/Algebraic_properties_of_line_digraphs

What I noticed in the introduction was that:

"As it is expected, it is not possible, to reconstruct the adjacency matrix of a digraph from the spectrum or the characteristic polynomial only. However we shall prove that this is possible for the case of line digraphs."

The paper claims to do this using a relation between the Jordan normal forms of the adjacency matrices of the digraph and its line digraph, which I am firstly unable to see clearly from the paper.

Secondly, given any graph, I could convert it into a digraph in the natural way by having two arcs for each of its edges. Then given the spectrum of a graph, we could construct the spectrum of its line digraph, from which I could reconstruct the line digraph (accordin to the paper's claim), from which I could in turn reconstruct the digraph (this correspondence between a digraph and its line digraph is well-understood in the case of digraphs with no sources or sinks- from the result of Harary and Norman) from which we could construct the underlying graph.

What am I missing here?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.