The Path Resistance Method for Bounding the Smallest Nontrivial Eigenvalue of a Laplacian

Abstract

We introduce the path resistance method for lower bounds on the smallest nontrivial eigenvalue of the Laplacian matrix of a graph. The method is based on viewing the graph in terms of electrical circuits: it uses clique embeddings to produce lower bonds on lambda2 and star embeddings to produce lower bounds on the smallest Rayleight quotient when there is a zero Dirichlet boundary condition. The method assigns priorities to the paths in the embedding: we show that for an unweighted tree T, using uniform priorities for a clique embedding produce a lower bound on lambda2 that is off by at most an O(log diameter(T)) factor. We show that the best bounds this method can produce for clique embeddings are the same as for a related method that uses clique embeddings and edge lengths to produce bounds.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1997
Accession Number
ADA331682

Entities

People

  • Gary L. Miller
  • Stephen Guattery
  • Tom Leighton

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Boundaries
  • Computer Science
  • Contracts
  • Differential Equations
  • Eigenvalues
  • Electrical Circuits
  • Embedding
  • Equations
  • Inequalities
  • Markov Chains
  • Mathematics
  • Networks
  • Partial Differential Equations
  • Resistance
  • Space Sciences

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.