Problem Detail: Given an adjacency matrix $A_G$ of an undirected graph $G$, it is easy and straightforward to compute the characteristic polynomial $chi_G(lambda)$. What about the other way around? The problem can be formulated as follows.
Problem Given a polynomial $P$, decide whether there is a graph $G$ with the corresponding adjacency matrix $A_G$ such that its characteristic polynomial $chi_G(lambda)$ equals the given $P$.
For an arbitrary $P$, it is not always the case that there is a corresponding $A_G$. The naive exhaustive algorithm for the problem uses a basic theorem in algebraic graph theory:
Theorem Let $G=(V,E)$ be a graph with adjacency matrix $A_G$ and $chi_G(lambda) = lambda^n+c_1lambda^{n-1}+c_2lambda^{n-2}+cdots+c_{n-1}lambda+c_n$, then (1) $c_1=0$, (2) $-c_2 = |E|$, and (3) $-c_3 = text{twice the # of triangles in G}$.
Now, given $P$, the algorithm goes through every candidate $A_G$ of a corresponding $G$ with $|E|=-c_2$ and number of triangles ($K_3$) equal to $-c_3$. For each $A_G$, compute $text{det}(A_G – lambda I)$ and see if it equals the given $P$. If none match, return false. Otherwise, return the $A_G$. This works, but is clearly not fast. The exhaustive algorithm would work even without the above theorem. Its use makes the search space smaller. What’s a fast and more clever algorithm?
Asked By : Juho
Answered By : Jernej
The short answer is
no. No quick algorithm for this problem is known. A big open problem (for at least 50 years) in algebraic graph theory asks about the existence a regular graph of degree 57 order 3250 girth 5 and diameter 2. This is known as a
Moore graph. However, it is known that if such a graph exists its characteristic polynomial has to be $p(x) = (x-57)(x+8)^{1520}(x-7)^{1729}$ [1, Proposition 1]. So if there would be a quick solution to your problem, this big open problem would be solved already. In fact, the theorem that you stated can be further generalized. The $i$’th coefficient of the characteristic polynomial of $G$ is given by $$(-1)^{i}c_i = sum (-1)^{r(H)} 2^{s(H)}$$ where the summation is taken over all subgraphs $H$ of $G$ that have order $i$ and whose connected components are $K_2$ and cycles. The function $s(H)$ counts the number of components of $H$ that are cycles while $r(H)$ denotes the
rank of $H.$ [1] M. Macaj, J. Siran. Search for properties of the missing Moore graph, Linear Algebra Appl., 432 (2010), 2381–2398.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6115 3.2K people like this
Download Related Notes/Documents
Related
