On the power of combinatorial and spectral invariants

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. (C) 2009 Elsevier Inc. All rights reserved.

Published in:
Linear Algebra And Its Applications, 432, 2373-2380
Presented at:
Workshop on Spectral Graph Theory, Rio de Janeiro, BRAZIL, Dec 01-04, 2008

 Record created 2011-12-16, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)