6
$\begingroup$

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_1\lambda^{n-1}+c_2\lambda^{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?

$\endgroup$
7
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you know anything about an algorithm for the problem? For example, what is the fastest known algorithm? $\endgroup$ – Juho Oct 27 '12 at 23:30
  • $\begingroup$ I don't think any real work has been done in this direction since I suspect the algorithm will (in general) always require searching for graphs in an exponential space. At best you can use some known results (see for example Spectra of graphs by Doob et. al.) that relate the eigenvalues to structural properties of graphs, that will in turn reduce the search space. $\endgroup$ – Jernej Oct 28 '12 at 9:58
  • $\begingroup$ @Juho BTW, a problem that is related to yours and is also a BIG open problem is to determine if for a given graph $G$ with char poly $p(x)$ there exist a nonisomorphic graph $G'$ with charpoly $p'(x)$ such that $p'(x) = p(x).$ It is belived that almost all graphs are determined by the respective charpoly but this is a big open problem since it would in turn allow to solve the isomorphism problem efficiently. $\endgroup$ – Jernej Oct 28 '12 at 10:04

Your Answer

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

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