Multiplicity of integer roots of polynomials of graphs

DOI10.1016/0024-3795(93)00337-YMaRDI QIDQ1902110zbMATH OpenWikidataFDO

Authors Isabel Faria

Publication date 14 November 1995

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(93)00337-Y

zbMATH Keywords

adjacency matrixcharacteristic polynomialsinteger rootsLaplacian matrixmultiplicitiespermanental polynomial

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Determinants, permanents, traces, other special matrix functions (15A15)

Review text

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\).

Recommendations

• Permanental roots and the star degree of a graph
• scientific article; zbMATH DE number 2140696
• Permanent of the Laplacian matrix of trees and bipartite graphs
• The permanent of the Laplacian matrix of a bipartite graph
• scientific article; zbMATH DE number 4196005

Cites work

• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• Laplace eigenvalues of graphs---a survey
• Laplacian matrices of graphs: A survey
• Matching theory
• Permanental polynomials of graphs
• Permanental roots and the star degree of a graph
• Permanents
• The Laplacian Spectrum of a Graph
• The Laplacian Spectrum of a Graph II

Cited in

(13)

• Laplacian graph eigenvectors
• Laplacian matrices of graphs: A survey
• On the (signless) Laplacian permanental polynomials of graphs
• Further results on the star degree of graphs
• Graphs and the multiplicity of root 2 in chromatic polynomials
• Shifted simplicial complexes are Laplacian integral
• scientific article; zbMATH DE number 6310920 (Why is no real title available?)
• On the roots of (signless) Laplacian permanental polynomials of graphs
• Strictly chordal graphs: structural properties and integer Laplacian eigenvalues
• On the second immanantal polynomials of graphs
• Some unicyclic graphs determined by the signless Laplacian permanental polynomial
• On some building blocks of hypergraphs
• Permanental roots and the star degree of a graph

This page was built for publication: Multiplicity of integer roots of polynomials of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1902110)