Accession Number:

ADA184430

Title:

Graph Partitioning by Eigenvectors,

Descriptive Note:

Corporate Author:

CLARKSON UNIV POTSDAM NY DEPT OF MATHEMATICS AND COMPUTER SCIENCE

Personal Author(s):

Report Date:

1987-01-01

Pagination or Media Count:

16.0

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE