Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 0796.05066
Bolla, Marianna; Tusnády, Gábor
Spectra and optimal partitions of weighted graphs.
(English)
[J] Discrete Math. 128, No.1-3, 1-20 (1994). ISSN 0012-365X

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\par 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.
MSC 2000:
*05C50 Graphs and matrices

Keywords: Laplacian; weighted graphs; eigenvectors; eigenvalues; spectrum

Cited in: Zbl 0973.05054

Highlights
Master Server