Foster's Formulas via Probability and the Kirchhoff Index

José Luis Palacios ()
Additional contact information
José Luis Palacios: Universidad Simón Bolívar

Methodology and Computing in Applied Probability, 2004, vol. 6, issue 4, 381-387

Abstract: Abstract Building on a probabilistic proof of Foster’s first formula given by Tetali (1994), we prove an elementary identity for the expected hitting times of an ergodic N-state Markov chain which yields as a corollary Foster’s second formula for electrical networks, namely $$\sum {R_{ij} } \frac{{C_{iv} C_{vj} }}{{C_v }} = N - 2,$$ where R ij is the effective resistance, as computed by means of Ohm’s law, measured across the endpoints of two adjacent edges (i,v) and (i,v), C iv and C iv are the conductances of these edges, C v is the sum of all conductances emanating from the common vertex v, and the sum on the left hand side of (1) is taken over all adjacent edges. We show how to extend Foster’s first and second formulas. As an application, we show how to use a “third formula” to compute the Kirchhoff index of a class of graphs with diameter 3.

Keywords: effective resistance; geodetic graphs (search for similar items in EconPapers)
Date: 2004
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1023/B:MCAP.0000045086.76839.54 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:6:y:2004:i:4:d:10.1023_b:mcap.0000045086.76839.54

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1023/B:MCAP.0000045086.76839.54

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().