MULTIPLICITY OF INTEGER ROOTS OF POLYNOMIALS OF GRAPHS

Let G be a graph with minimum vertex degree p greater than or equal to 1. Let B = D + A, where D is the diagonal matrix of vertex degrees and A is the adjacency matrix of C. The multiplicity of the integer root p of per(xI - B) is characterized. For bipartite graphs, this characterization extends to per(xI - L), where L = D - A is the Laplacian matrix of G. For graphs with unrestricted vertex degrees, bounds are obtained on the multiplicities of integer roots of the permanental and characteristic polynomials of both L and B.