Multiplicity of integer roots of polynomials of graphs (Q1902110): Difference between revisions

Let \(G\) be a graph and let \(\delta\) be the minimal degree of vertices in \(G\). Let \(B= D+ A\), where \(D\) is the diagonal matrix of vertex degrees and \(A\) is the adjacency matrix of \(G\). A combinatorial characterization is given for the multiplicity of \(\delta\) as the root of the permanental polynomial \(\text{per}(xI- B)\). If \(G\) is bipartite, this characterization extends to \(\text{per}(xI- L)\), where \(L= D- A\) is the Laplacian matrix of \(G\). These results are also extended to results about multiplicities of (arbitrary) integer roots of the permanental and the characteristic polynomials of both \(B\) and \(L\).