Spectra and optimal partitions of weighted graphs. (English) Zbl 0796.05066

Authors’ abstract: The notion of the Laplacian of weighted graphs will be introduced, the eigenvectors belonging to \(k\) consecutive eigenvalues which define an optimal \(k\)-dimensional
Euclidean representation of the vertices. By means of these spectral techniques some combinatorial problems concerning minimal \((k+1)\)-cuts of weighted graphs can be handled easily with linear algebraic tools. (Here \(k\) is an arbitrary integer between 1 and the number of vertices.) The \((k+1)\)-variance of the optimal \(k\)-dimensional representatives is estimated from above by the \(k\) smallest positive eigenvalues and by the gap in the spectrum between the \(k\)-th and \((k+1)\)-th positive eigenvalues in increasing order.


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


[1] Alon, N., Eigenvalues and Expanders, Combinatorica, 6, 2, 83-96 (1986) · Zbl 0661.05053
[2] Biggs, N. L., Algebraic Graph Theory (1974), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0501.05039
[3] Bolla, M., Techniques and statistical applications of the singular value decomposition of matrices, Ph.D. Thesis (1982), in Hungarian
[4] Bolla, M., Spectra, Euclidean representations and clusterings of Hypergraphs, Discrete Math., 117, 13-39 (1993) · Zbl 0781.05036
[5] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs (1979), Academic Press: Academic Press New York, San Francisco, London
[6] Dunn, J. C., Well-separated clusters and optimal fuzzy partitions, J. Cybernetics, 4, 1, 95-104 (1974) · Zbl 0304.68093
[7] Dunn, J. C., Some recent investigations of a new fuzzy partitioning algorithm and its application to pattern classification problems, 4, 2, 1-23 (1974) · Zbl 0304.68094
[8] Hoffman, A. J., On eigenvalues and colorings of graphs, (Harris, B., Graph Theory and its applications (1970), Academic Press: Academic Press New York, London), 79-91
[9] Mac Queen, J., Some methods for classification and analysis of multivariate observations, Proc. 5th Berkeley Symp. Math. Statist. Prob., Vol. 1, 281-297 (1967)
[10] Rao, C. R., Separation theorems for singular values of matrices and their applications in multivariate analysis, J. Multivariate Anal., 9, 362-377 (1979) · Zbl 0445.62069
[11] Simonovits, M., Extermal graph problems, degenerate extremal problems and supersaturated graphs, (Progress in Graph Theory (1984), Academic Press: Academic Press New York), 419-437
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.