Edge-matching graph contractions and their interlacing properties

DOI10.1016/j.laa.2020.11.003zbMath1459.05178arXiv2002.11842OpenAlexW3099469401MaRDI QIDQ2228529

Noam Leiter, Daniel Zelazo

Publication date: 17 February 2021

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

Full work available at URL: https://arxiv.org/abs/2002.11842

zbMATH Keywords

spectral clusteringgraph contractionsLaplacian interlacing

Mathematics Subject Classification ID

Partial orders, general (06A06) Trees (05C05) Partitions of sets (05A18) Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eigenvalues, singular values, and eigenvectors (15A18) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Graph clustering
• Compact graphs and equitable partitions
• Interlacing eigenvalues on some operations of graphs
• An algorithm for the enumeration of spanning trees
• Interlacing eigenvalues and graphs
• An Interlacing Result on Normalized Laplacians
• Finding Connected Components in O(log n log log n) Time on the EREW PRAM
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item