Edge-matching graph contractions and their interlacing properties

DOI10.1016/J.LAA.2020.11.003MaRDI QIDQ2228529zbMATH OpenOpenAlexFDO

Authors 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

graph contractionsLaplacian interlacingspectral clustering

Mathematics Subject Classification ID

Partitions of sets (05A18) Trees (05C05) 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) Graph algorithms (graph-theoretic aspects) (05C85) Partial orders, general (06A06) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: For a given graph $mathcalG$ of order $n$ with $m$ edges, and a real symmetric matrix associated to the graph, $Mleft(mathcalGight)inmathbb{R}^{nimesn}$, the interlacing graph reduction problem is to find a graph $mathcal{G}_r$ of order $r<n$ such that the eigenvalues of $Mleft(mathcal{G}_{r}ight)$ interlace the eigenvalues of $Mleft(mathcalGight)$. Graph contractions over partitions of the vertices are widely used as a combinatorial graph reduction tool. In this study, we derive a graph reduction interlacing theorem based on subspace mappings and the minmax theory. We then define a class of edge-matching graph contractions and show how two types of edge-matching contractions provide Laplacian and normalized Laplacian interlacing. An $mathcalOleft(mnight)$ algorithm is provided for finding a normalized Laplacian interlacing contraction and an $mathcalOleft(n^2+nmight)$ algorithm is provided for finding a Laplacian interlacing contraction.

Recommendations

• Interlacing results on matrices associated with graphs
• Interlacing eigenvalues on some operations of graphs
• Deleting vertices and interlacing Laplacian eigenvalues
• An Interlacing Result on Normalized Laplacians
• On the spectrum of the normalized Laplacian for signed graphs: interlacing, contraction, and replication

Cites work

• An algorithm for the enumeration of spanning trees
• An Interlacing Result on Normalized Laplacians
• Asymptotic expansions of central binomial coefficients and Catalan numbers
• Compact graphs and equitable partitions
• Finding Connected Components in O(log n log log n) Time on the EREW PRAM
• Graph clustering
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3961334 (Why is no real title available?)
• scientific article; zbMATH DE number 3681933 (Why is no real title available?)
• scientific article; zbMATH DE number 194139 (Why is no real title available?)
• scientific article; zbMATH DE number 729555 (Why is no real title available?)
• scientific article; zbMATH DE number 1034200 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Interlacing eigenvalues and graphs
• Interlacing eigenvalues on some operations of graphs

Cited in

(3)

• scientific article; zbMATH DE number 1222899 (Why is no real title available?)
• Edge contractions in subclasses of chordal graphs
• Edge proximity and matching extension in projective planar graphs

This page was built for publication: Edge-matching graph contractions and their interlacing properties

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