
Accession Number : ADA184430
Title : Graph Partitioning by Eigenvectors,
Corporate Author : CLARKSON UNIV POTSDAM NY DEPT OF MATHEMATICS AND COMPUTER SCIENCE
Personal Author(s) : Powers, David L
PDF Url : ADA184430
Report Date : Jan 1987
Pagination or Media Count : 16
Abstract : Let A be the adjacency matrix of a connected graph G. If z is a column vector, we say that a vertex of G is positive, nonnegative, null, etc. if the corresponding entry of z has that property. For z such that Az or = alpha z, we bound the number of components in the subgraph induced by positive vertices. For eigenvectors z having a null element, we bound the number of components in the graph induced by nonnull vertices. Finally, bounds are established for the number of null elements in an eigenvector, for the multiplicity of an eigenvalue and for the magnitudes of the second and last eignevalues of a general or a bipartite graph.
Descriptors : *LINEAR ALGEBRA, *GRAPHS, EIGENVECTORS, SYMMETRY, MATRIX THEORY
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE