Polynomial Relations Between Matrices of Graphs

Abstract

We derive a correspondence between the eigenvalues of the adjacency matrix $A$ and the signless Laplacian matrix $Q$ of a graph $G$ when $G$ is $(d_1,d_2)$-biregular by using the relation $A^2=(Q-d_{1}I)(Q-d_{2}I)$. This motivates asking when it is possible to have $X^r=f(Y)$ for $f$ a polynomial, $r>0$, and $X,Y$ matrices associated to a graph $G$. It turns out that, essentially, this can only happen if $G$ is either regular or biregular.

16 pages