Advanced Search

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.
[A.Torgašev (Beograd)]

MSC 2000:: *05C50 Graphs and matrices

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

Cited in: Zbl 0973.05054

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]