Search

In [3,4] the authors found formulas for the number of spanning 2-forests (equivalently for the resistance distance) between any pair of vertices in a "straight linear 2-tree" and in a "linear 2-tree with a single bend." The main result of this paper generalizes these formulas to linear 2-trees with any number of bends. We also give alternative and perhaps more transparent versions of these formulas in terms of block matrices. As an application we find the resistance distance between the extremal vertices of the "corrugated linear 2-tree" and use this result to determine its asymptotic rate of growth as the number of vertices goes to infinity. Finally we note that our formulas give a different way to determine all the resistance distances in a "fan graph." [ABSTRACT FROM AUTHOR]

A spanning 2-forest separating vertices u and v of an undirected connected graph is a spanning forest with 2 components such that u and v are in distinct components. Aside from their combinatorial significance, spanning 2-forests have an important application to the calculation of resistance distance or effective resistance. The resistance distance between vertices u and v in a graph representing an electrical circuit with unit resistance on each edge is the number of spanning 2-forests separating u and v divided by the number of spanning trees in the graph. There are also well-known matrix theoretic methods for calculating resistance distance, but the way in which the structure of the underlying graph determines resistance distance via these methods is not well understood. For any connected graph G with a 2-separator separating vertices u and v , we show that the number of spanning trees and spanning 2-forests separating u and v can be expressed in terms of these same quantities for the smaller separated graphs, which makes computation significantly more tractable. An important special case is the preservation of the number of spanning 2-forests if u and v are in the same smaller graph. In this paper we demonstrate that this method of calculating resistance distance is more suitable for certain structured families of graphs than the more standard methods. We apply our results to count the number of spanning 2-forests and calculate the resistance distance in a family of Sierpinski triangles and in the family of linear 2-trees with a single bend. [ABSTRACT FROM AUTHOR]

Abstract We consider the graph G n with vertex set V (G n) = { 1 , 2 , ... , n } and { i , j } ∈ E (G n) if and only if 0 < | i − j | ≤ 2. We call G n the straight linear 2-tree on n vertices. Using Δ –Y transformations and identities for the Fibonacci and Lucas numbers we obtain explicit formulae for the resistance distance r G n (i , j) between any two vertices i and j of G n. To our knowledge { G n } n = 3 ∞ is the first nontrivial family with diameter going to ∞ for which all resistance distances have been explicitly calculated. Our result also gives formulae for the number of spanning trees and 2-forests in a straight linear 2-tree. We show that the maximal resistance distance in G n occurs between vertices 1 and n and the minimal resistance distance occurs between vertices n ∕ 2 and n ∕ 2 + 1 for n even (with a similar result for n odd). It follows that r n (1 , n) → ∞ as n → ∞. Moreover, our explicit formula makes it possible to order the non-edges of G n exactly according to resistance distance, and this ordering agrees with the intuitive notion of distance on a graph. Consequently, G n is a geometric graph with entirely different properties than the random geometric graphs investigated in Luxburg, Radl and Hein (2010). These results for straight linear 2-trees along with an example of a bent linear 2-tree and empirical results for additional graph classes convincingly demonstrate that resistance distance should not be discounted as a viable method for link prediction in geometric graphs. [ABSTRACT FROM AUTHOR]