Deletion-contraction for a unified Laplacian and applications

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.