On the power of combinatorial and spectral invariants

DOI10.1016/J.LAA.2009.07.019MaRDI QIDQ962126zbMATH OpenOpenAlexFDO

Authors Martin Fürer

Publication date 6 April 2010

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2009.07.019

zbMATH Keywords

edge coloringspectral propertiesstarlike trees2-dim W-L

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Coloring of graphs and hypergraphs (05C15)

Recommendations

• New invariants for the graph isomorphism problem
• scientific article; zbMATH DE number 4139784
• scientific article; zbMATH DE number 193703
• A study of eigenspaces of graphs
• A matrix representation of graphs and its spectrum as a graph invariant

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 910921 (Why is no real title available?)
• An optimal lower bound on the number of variables for graph identification
• Constructing trees with given eigenvalues and angles
• Eigenspaces of graphs
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• No starlike trees are cospectral
• On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
• Random Graph Isomorphism
• Some trees characterized by eigenvalues and angles
• The graph isomorphism disease

Cited in

(11)

• Optimization and highly informative graph invariants
• scientific article; zbMATH DE number 193703 (Why is no real title available?)
• On the combinatorial power of the Weisfeiler-Lehman algorithm
• On the expressive power of linear algebra on graphs
• On the Weisfeiler-Leman dimension of fractional packing
• New invariants for the graph isomorphism problem
• On the expressive power of linear algebra on graphs
• Combinatorial invariants computing the Ray-Singer analytic torsion
• Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements
• On Weisfeiler-Leman invariance: subgraph counts and related graph properties
• scientific article; zbMATH DE number 44782 (Why is no real title available?)

This page was built for publication: On the power of combinatorial and spectral invariants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q962126)