Department of Mathematics, University of Rhode Island, Kingston, Rhode Island, U.S.A.

In 1989, Stephenson and Zelen derived an elegant formula for the information I_{ab} contained in all possible paths between two nodes a and b in a network, which is described as follows. Given a finite weighted graph G and its Laplacian matrix L, the *combinatorial Green’s function* \(\mathcal{G}\), of G is the inverse of L+J, where J is the all 1’s matrix. Then, it was shown that I_{ab}=(g_{aa}+g_{bb}-2g_{ab})^{-1}, where g_{ij} is the (i,j)-th entry of \(\mathcal{G}\). In this talk, we prove an intriguing combinatorial formula for I_{ab}:

where \(\kappa(G)\) is the complexity, or tree-number, of G, and G_{a*b} is obtained from G by identifying two vertices a and b. We will discuss several implications of this new formula, including the equivalence of I_{ab} and the effective conductance between two nodes in electrical networks.

Tags: 국웅