Deletion-contraction for a unified Laplacian and applications
January 18, 2022
We define a graph Laplacian with vertex weights in addition to the more classical edge weights, which unifies the combinatorial Laplacian and the normalised Laplacian. Moreover, we give a combinatorial interpretation for the coefficients of the weighted Laplacian characteristic polynomial in terms of weighted spanning forests and use this to prove a deletion-contraction relation. We will see applications to some of: eigenvalue interlacing theorems, sparse cuts, independent sets, proper colourings, constructing cospectral graphs and isomorphism problems in graph theory.
Joint work with Farid Aliniaeifard and Steph van Willigenburg.
Event Details
January 18, 2022
4:00pm to 5:00pm
Zoom - https://ubc.zoom.us/j/62676242229?pwd=RURtUC9UYXEweVZTMTNGT1EvY1FLZz09
Vancouver, BC, CA
V6T1Z2