zbMATH — the first resource for mathematics

Multiplicity of integer roots of polynomials of graphs. (English) Zbl 0843.05074
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\).

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A15 Determinants, permanents, traces, other special matrix functions
Full Text: DOI
[1] Cvetkovic, D.; Doob, M.; Sachs, H., Spectra of graphs, (1980), Academic New York · Zbl 0458.05042
[2] Faria, I., Permanental roots and the star degree of a graph, Linear algebra appl., 64, 255-265, (1985) · Zbl 0559.05041
[3] Grone, R.; Merris, R.; Sunder, V., The Laplacian spectrum of a graph, SIAM J. matrix anal. appl., 11, 2, 218-238, (1990) · Zbl 0733.05060
[4] R. Grone, and R. Merris, The Laplacian spectrum of a graph II, manuscript. · Zbl 0795.05092
[5] L. Lovasz and M. Plummer, Matching Theory, Math. Studies 121, Ann. Discrete Math. 29, North-Holland. · Zbl 0618.05001
[6] Merris, R., Laplacian matrices of graphs: A survey, () · Zbl 0802.05053
[7] Merris, R.; Rebman, K.; Watkins, W., Permanental polynomials of graphs, Linear algebra appl., 38, 273-288, (1981) · Zbl 0474.05049
[8] Minc, H., Permanents, (1987), Addison-Wesley · Zbl 0166.29904
[9] Mohar, B., Laplace eigenvalues of graphs—a survey, Discrete math., 109, 171-183, (1992) · Zbl 0783.05073
[10] Mohar, B.; Poljak, S., Eigenvalues in combinatorial optimization, Preprint ser. dept. math. univ. EK Ljubljana, 30, 1-61, (1992)
[11] Mohar, B., The Laplacian spectrum of graphs, Preprint ser. dept. math. univ. EK Ljubljana, 30, 353-384, (1988)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.