Graph Partitioning by Eigenvectors,
CLARKSON UNIV POTSDAM NY DEPT OF MATHEMATICS AND COMPUTER SCIENCE
Pagination or Media Count:
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.
- Theoretical Mathematics