Pebble games and cospectral graphs

DOI10.1016/J.ENDM.2017.06.055MaRDI QIDQ1689933zbMATH OpenOpenAlexFDO

Authors Anuj Dawar, Simone Severini, Octavio Zapata

Publication date 18 January 2018

Full work available at URL https://doi.org/10.1016/j.endm.2017.06.055

zbMATH Keywords

combinatorial gamesgraph spectraisomorphism approximations

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Games on graphs (graph-theoretic aspects) (05C57) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Games involving graphs (91A43)

Recommendations

• Pebble games and linear equations

Cites work

• Infinitary logics and 0-1 laws
• Logical hierarchies in PTIME
• The pebbling comonad in finite model theory
• Which graphs are determined by their spectrum?

Cited in

(6)

• Sparse hypergraphs and pebble game algorithms
• PEBBLE GAMES AND LINEAR EQUATIONS
• scientific article; zbMATH DE number 4189511 (Why is no real title available?)
• On the Weisfeiler-Leman dimension of fractional packing
• On Weisfeiler-Leman invariance: subgraph counts and related graph properties
• A categorical account of composition methods in logic

This page was built for publication: Pebble games and cospectral graphs

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