The critical polynomial of a graph

Abstract

Let $G$ be a connected graph on $n$ vertices with adjacency matrix $A_G$. Associated to $G$ is a polynomial $d_G(x_1,\dots ,x_n)$ of degree $n$ in $n$ variables, obtained as the determinant of the matrix $M_G(x_1,\dots ,x_n)$, where $M_G=\mathrm{Diag}(x_1,\dots ,x_n)-A_G$. We investigate in this article the set $V_{d_G}(r)$ of non-negative values taken by this polynomial when $x_1,\dots ,x_n\ge r\ge 1$. We show that $V_{d_G}(1)={\mathbb{Z}}_{\ge 0}$. We show that for a large class of graphs one also has $V_{d_G}(2)={\mathbb{Z}}_{\ge 0}$. When $V_{d_G}(2)\ne {\mathbb{Z}}_{\ge 0}$, we show that for many graphs $V_{d_G}(2)$ is dense in ${\mathbb{Z}}_{\ge 0}$. We give numerical evidence that in many cases, the complement of $V_{d_G}(2)$ in ${\mathbb{Z}}_{\ge 0}$ might in fact be finite. As a byproduct of our results, we show that every graph can be endowed with an arithmetical structure whose associated group is trivial.