Edge-matching graph contractions and their interlacing properties

DOI10.1016/J.LAA.2020.11.003zbMATH Open1459.05178arXiv2002.11842OpenAlexW3099469401MaRDI QIDQ2228529FDOQ2228529

Noam Leiter, Daniel Zelazo

Publication date: 17 February 2021

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

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.

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

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

zbMATH Keywords

spectral clusteringgraph contractionsLaplacian interlacing

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• Edge proximity and matching extension in projective planar graphs
• Edge contractions in subclasses of chordal 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)