Graph Partitioning by Eigenvectors,

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1987
Accession Number
ADA184430

Entities

People

  • David L. Powers

Organizations

  • Clarkson University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algebra
  • Algorithms
  • Computer Science
  • Differential Equations
  • Eigenvalues
  • Eigenvectors
  • Equations
  • Graph Theory
  • Inequalities
  • Interlacing
  • Linear Programming
  • Mathematical Analysis
  • Mathematics
  • Matrix Theory
  • New York
  • Spectra
  • Theorems

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Linear Algebra