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 non-null 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