Combinatorial Green's Function of a Graph and Applications to Networks
Advances in Applied Mathematics, 46 (1–4):
417--423 (2011)Special issue in honor of Dennis Stanton.DOI: 10.1016/j.aam.2010.10.006
Abstract
Given a finite weighted graph G and its Laplacian matrix L, the combinatorial Greenʼs function G of G is defined to be the inverse of L + J , where J is the matrix each of whose entries is 1. We prove the following intriguing identities involving the entries in G = ( g i j ) whose rows and columns are indexed by the vertices of G: g a a + g b b − g a b − g b a = κ ( G a ⁎ b ) / κ ( G ) , where κ ( G ) is the complexity or tree-number of G, and G a ⁎ b is obtained from G by identifying two vertices a and b. As an application, we derive a simple combinatorial formula for the resistance between two arbitrary nodes in a finite resistor network. Applications to other similar networks are also discussed.
