Eigenvalues of the Laplacian of a graph. (English) Zbl 0594.05046

From the authors’ abstract: ”Let G be a finite undirected graph with no loops or multiple edges. The Laplacian matrix \(\Delta\) (G) of G is defined by \(\Delta_{ii}\) \(=\) the degree of vertex i, and \(\Delta_{ij}=-1\) if there is an edge between vertex i and vertex j. In this paper the structure of the graph G is related to the eigenvalues of \(\Delta\) (G). It is proved that all eigenvalues of \(\Delta\) (G) are non- negative, do not exceed the number of vertices, and do not exceed twice the maximum vertex degree. The exact conditions for equalities are also given.”
Reviewer: A.Torgašev


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI Link


[1] Doob M., Linear Algebra and Appl. 3 pp 461– (1970) · Zbl 0202.55703
[2] Fisher M. E., J. Comb. Theory pp 105– (1966) · Zbl 0139.43302
[3] Forsythe G. I., Finite-Difference Methods for Partial Differential Equations (1960) · Zbl 0099.11103
[4] Gantmacher F R., Theory of Matrices (1959) · Zbl 0085.01001
[5] Harary F., Graph Theory (1969)
[6] Hoffman A. J, Some recent results on spectral properties of graphs, in Beiträg zur Graphentheoric (1968) · Zbl 0167.52202
[7] Fiedler M., Czech. Math. J. 23 pp 298– (1973)
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.