Mathematics – Combinatorics
Scientific paper
2006-12-27
Discrete Applied Mathematics 156 (2008) 813-821
Mathematics
Combinatorics
12 pages, 2 figures, 25 references. As accepted by Disc. Appl. Math. (2007)
Scientific paper
10.1016/j.dam.2007.08.030
For a graph G, let f_{ij} be the number of spanning rooted forests in which vertex j belongs to a tree rooted at i. In this paper, we show that for a path, the f_{ij}'s can be expressed as the products of Fibonacci numbers; for a cycle, they are products of Fibonacci and Lucas numbers. The {\em doubly stochastic graph matrix} is the matrix F=(f_{ij})/f, where f is the total number of spanning rooted forests of G and n is the number of vertices in G. F provides a proximity measure for graph vertices. By the matrix forest theorem, F^{-1}=I+L, where L is the Laplacian matrix of G. We show that for the paths and the so-called T-caterpillars, some diagonal entries of F (which provides a measure of the self-connectivity of vertices) converge to \phi^{-1} or to 1-\phi^{-1}, where \phi is the golden ratio, as the number of vertices goes to infinity. Thereby, in the asymptotic, the corresponding vertices can be metaphorically considered as "golden introverts" and "golden extroverts," respectively. This metaphor is reinforced by a Markov chain interpretation of the doubly stochastic graph matrix, according to which F equals the overall transition matrix of a random walk with a random number of steps on G.
No associations
LandOfFree
Spanning Forests and the Golden Ratio does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Spanning Forests and the Golden Ratio, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanning Forests and the Golden Ratio will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-335319