TY - JOUR
T1 - On the power of combinatorial and spectral invariants
AU - Fürer, Martin
N1 - Funding Information:
E-mail address: [email protected] URL: http://www.cse.psu.edu/∼furer 1 Research supported in part by NSF Grant CCF-0728921. 2 Visiting: ALGO, EPFL, CH-1015 Lausanne, Switzerland, and Mathematik, Universität Zürich, CH-8057 Zürich, Switzerland.
PY - 2010/4/15
Y1 - 2010/4/15
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=77049114501&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77049114501&partnerID=8YFLogxK
U2 - 10.1016/j.laa.2009.07.019
DO - 10.1016/j.laa.2009.07.019
M3 - Article
AN - SCOPUS:77049114501
SN - 0024-3795
VL - 432
SP - 2373
EP - 2380
JO - Linear Algebra and Its Applications
JF - Linear Algebra and Its Applications
IS - 9
ER -