Algebraic properties of generalized graph laplacians: Resistor networks, critical groups, and homological algebra^∗

We propose an algebraic framework for generalized graph Laplacians which unifies the study of resistor networks, the critical group, and the eigenvalues of the Laplacian and adjacency matrices. Given a graph with boundary G together with a generalized Laplacian L with entries in a commutative ring R, we define a generalized critical group Υ_R(G, L). We relate Υ_R(G, L) to spaces of harmonic functions on the network using the Hom, Tor, and Ext functors of homological algebra. We study how these algebraic objects transform under combinatorial operations on the network (G, L), including harmonic morphisms, layer-stripping, duality, and symmetry. In particular, we use layer-stripping operations from the theory of resistor networks to systematize discrete harmonic continuation. This leads to an algebraic characterization of the graphs with boundary that can be completely layer-stripped, an algorithm for simplifying computation of Υ_R(G, L), and upper bounds for the number of invariant factors in the critical group and the multiplicity of Laplacian eigenvalues in terms of geometric quantities.