On the power of combinatorial and spectral invariants

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

We extend the traditional spectral invariants (spectrum and angles) by a stronger polynomial time computable graph invariant based on the angles between projections of standard basis vectors into the eigenspaces (in addition to the usual angles between standard basis vectors and eigenspaces). The exact power of the new invariant is still an open problem. We also define combinatorial invariants based on standard graph isomorphism heuristics and compare their strengths with the spectral invariants. In particular, we show that a simple edge coloring invariant is at least as powerful as all these spectral invariants.

Original languageEnglish (US)
Pages (from-to)2373-2380
Number of pages8
JournalLinear Algebra and Its Applications
Volume432
Issue number9
DOIs
StatePublished - Apr 15 2010

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On the power of combinatorial and spectral invariants'. Together they form a unique fingerprint.

Cite this