The Critical Polynomials of Simple Connected Graphs

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}$.