The Critical Polynomials of Simple Connected Graphs

Source abstract

Let $G$ be a connected graph with $n$ vertices and adjacency matrix $A(G)$. The critical polynomial $d_G(x_1, \ldots, x_n)$ is a degree-$n$ multivariate polynomial defined as the determinant of the matrix $M_G(x_1, \ldots, x_n)$, where $$M_G(x_1,\ldots,x_n) = \operatorname{Diag}(x_1, \ldots, x_n) - A(G).$$ For any positive integer $r$, define the set $$V_{d_G}(r)=\{d_G(x_1,\ldots,x_n)\mid x_i\in\mathbb{Z}_{\ge r}, 1\le i\le n\}\cap \mathbb{Z}_{\ge 0},$$ where $\mathbb{Z}_{\ge r}$ denotes the set of all integers not less than $r$. The subset $V_G(r)\subseteq V_{d_G}(r)$ consists the elements $u$ such that there exist $a_1,\ldots,a_n\in\mathbb{Z}_{\ge r}$ for which $u=d_G(a_1,\ldots,a_n)$, the matrix $M_G(a_1,\ldots,a_n)$ is positive definite if $u\ne 0$ and positive semi-definite with rank $n-1$ if $u=0$. Furthermore, the associated group $\Phi_{M_G(a_1,\ldots,a_n)}$ must be cyclic. Motivated by Lorenzini's exploration of whether the complement of $V_{d_G}(2)$ in $\mathbb{Z}_{\geq 0}$ might be finite for typical graphs [J. Number Theory 257 (2024) 215-248], we establish that for any simple connected graph $G$, the subset $V_G(2)$ is dense in $\mathbb{Z}_{\geq 0}$. This provides additional evidence in support of Lorenzini's hypothesis that the larger subset $V_{d_G}(2)$ might actually be cofinite in $\mathbb{Z}_{\ge 0}$.