Polynomials and adjacency matrix of a graph

Question

If $p$ is some polynomial such that $[p(A)]_{ij} \neq 0$ and $A$ is the adjacency matrix of a graph. Does the existence of such a $p$ say anything about the graph?

Answer 1

I think it's more interesting when you have a polynomial $p$ such that $p(A)=0$. Such a polynomial tells us that if $p_{ij}(r)$ is the number of paths of length $r$ from $i$ to $j$, then $p_{ij}(r)$ satisfies a degree-$d$ recurrence (where $d=\mathrm{deg\,} p$) which is independent of $i$ and $j$. (By the Cayley-Hamilton theorem, the characteristic polynomial of $A$ is such a polynomial, so such a recurrence exists.)