Algebraic Graph Theory Seminar - Victor Wang

Monday, April 11, 2022 11:30 am - 11:30 am EDT (GMT -04:00)

Title: Deletion-contraction for a unified Laplacian and applications

Speaker: Victor Wang
Affiliation: University of British Columbia
Zoom: Contact Sabrina Lato


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.