A solution to Gutman's problem on the characteristic polynomial of a bipartite graph (Q1918564): Difference between revisions

Let \(\phi(G, x)= \sum^n_{k= 0} a(G, k) x^{n- k}\) be the characteristic polynomial of a graph \(G\), and define \[ \phi(G, x, y)= \sum^n_{k= 0} a(G, k) x^{n- k} y^{k/2}. \] The following recursion is obtained in this short note: \[ {\partial \phi(G, x, y)\over \partial y}= - \sum_{uv\in E(G)} \phi(G- u- v, x, y)- \sum_{C\in {\mathcal C}(G)} |C|y^{(|C|- 2)/2} \phi(G- V(C), x, y), \] where \({\mathcal C}(G)\) is the set of cycles in the graph \(G\). The proof is straightforward by comparing the coefficients of both sides. Note there is a typo in the second last line before equation (**): \(x^{2- 2k}\) should be \(x^{n- 2k}\).