On the power of combinatorial and spectral invariants |
| |
Authors: | Martin Fürer |
| |
Institution: | CSE, Pennsylvania State University, University Park, PA 16802, USA |
| |
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. |
| |
Keywords: | Edge coloring 2-dim W-L Spectral properties Starlike trees |
本文献已被 ScienceDirect 等数据库收录! |