The critical polynomial of a graph

Let G be a connected graph on n vertices with adjacency matrix A(G). Associated to G is a polynomial d(G)(x(1), . . . , x(n)) of degree n in n variables, obtained as the determinant of the matrix M-G(x(1), . . . , x(n)), where M-G = Diag(x(1), . . . , x(n)) - A(G). We investigate in this article the set V-dG(r) of non-negative values taken by this polynomial when x(1), . . . , x(n) >= r >= 1. We show that V-dG(1) = Z(>= 0). We show that for a large class of graphs one also has V-dG (2) = Z(>= 0). When V-dG (2) not equal Z(>= 0), we show that for many graphs V-dG (2) is dense in Z(>= 0). We give numerical evidence that in many cases, the complement of V-dG (2) in Z(>= 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.(c) 2023 Elsevier Inc. All rights reserved.