Cospectral Graph Complements and Generating Function of Walks

Question

Let $G$ and $H$ be cospectral graphs. How would one prove that the respective graph complements $\overline{G}$ and $\overline{H}$ are cospectral if and only if the generating functions for all walks in $G$ and in $H$ are equal? Note that, letting $A$ denote the adjacency matrix of $G$, this generating function can be found by $$\sum_{r\geq 0}\text{tr}(A^rJ)t^r$$ where $J$ is appropriately sized matrix where all entries are $1$. Additionally, could this proof be modeled from this previously asked question?

Answer 1

The characteristic polynomial of the complement of $G$ is $\det(tI+I+A-J)$. Now \[ \det(tI+I+A-J) = \det((t+1)I+A) \det(I - ((t+1)I+A)^{-1})J) \] and if we set $x= ((t+1)I+A)^{-1}\mathbf{1}$, then using the identity $\det(I-AB)=\det(I-BA)$ (Sylvester's determinant identity), we get \[ \det(I-x\mathbf{1}^T) = \det(I -\mathbf{1}^Tx) = 1 - \mathbf{1}^T ((t+1)I+A)^{-1} \mathbf{1}. \]

Next \[ ((t+1)I+A)^{-1} = (t+1)^{-1} (I+(t+1)^{-1}A)^{-1}) = \sum_{k\ge0} (-t-1)^kA^k \] and therefore \[ \frac{\det(tI+A+I-J)}{\det((t+1)I+A)} = 1 - \sum_{k\ge0} (-t-1)^k \mathbf{1}^TA^k\mathbf{1}. \] It follows that, given the characteristic polynomial of $G$, the characteristic polynomial of its complement is determined by (and determines) the sequence of numbers $\mathbf{1}^TA^k\mathbf{1}=\mathop{tr}(A^kJ)$.