Resistance distance

In graph theory, the resistance distance between two vertices of a simple connected graph, "G", is equal to the resistance between two equivalent points on an electrical network, constructed so as to correspond to "G", with each edge being replaced by a 1 ohm resistance. It is a metric on graphs.
Definition.
On a graph "G", the resistance distance Ω"i","j" between two vertices "vi" and "vj" is
where formula_2, with formula_3 denoting the Moore–Penrose inverse, formula_4 the Laplacian matrix of "G", formula_5 is the number of vertices in "G", and formula_6 is the formula_7 matrix containing all 1s.
Properties of resistance distance.
If "i" = "j" then
For an undirected graph
General sum rule.
For any "N"-vertex simple connected graph "G" = ("V", "E") and arbitrary "N"×"N" matrix "M":
From this generalized sum rule a number of relationships can be derived depending on the choice of "M". Two of note are;
where the formula_12 are the non-zero eigenvalues of the Laplacian matrix. This unordered sum is called the Kirchhoff index of the graph.
Relationship to the number of spanning trees of a graph.
For a simple connected graph "G" = ("V", "E"), the resistance distance between two vertices may be expressed as a function of the set of spanning trees, "T", of "G" as follows:
where formula_14 is the set of spanning trees for the graph formula_15.
As a squared Euclidean distance.
Since the Laplacian formula_4 is symmetric and positive semi-definite, so is formula_17, thus its pseudo-inverse formula_18 is also symmetric and positive semi-definite. Thus, there is a formula_19 such that formula_20 and we can write:
showing that the square root of the resistance distance corresponds to the Euclidean distance in the space spanned by formula_19.
Connection with Fibonacci numbers.
A fan graph is a graph on formula_23 vertices where there is an edge between vertex formula_24 and formula_23 for all formula_26 and there is an edge between vertex formula_24 and formula_28 for all formula_29
The resistance distance between vertex formula_30 and vertex formula_31
is formula_32 where formula_33 is the formula_34-th Fibonacci number, for formula_35.