Enumerating Spanning Trees And Random Walks On Deterministic Growing Networks

Deterministic networks are constructed by deterministic ways. Since they have deter-ministic topological structures, we can obtain the analytical expressions for the topologi-cal and dynamical properties and verify the correctness of random graphs. Enumeration of spanning trees and random walks are two topics in the research of deterministic net-works. Because of diverse network structures, obtaining the exact results is challenging and the relationship between spanning trees and random walks is not reported. In this dissertation, we calculate spanning trees and random works on three kinds of determin-istic growing networks, study the effect of some topologies on the entropy of spanning trees and random walks, and analyze the relationship between spanning trees and random walks. In details, the main contents of this dissertation are organized as follows:In Chapter I, we provide the research background and the current situation of the deterministic networks and introduce the enumeration of spanning trees and random walks on deterministic networks.In Chapter n, we obtain analytical expressions of spanning trees on prism and anti-prism graphs and Apollonian networks by the electrical equivalent transformations. We also compare the entropy of spanning trees of the existing networks from the view of average degree.In Chapter ?, we construct a family of treelike networks with time delay and two controlled parameters. We study three types of random walks, including mean receiving time, mean sending time and mean first passage time. We obtain their exact results and see that the efficiency of random walks decreases with the increasing of network parameters. Compared to the nondelayed trees, the efficiency of random walks in delayed trees is higher.In Chapter IV, we choose a family of pseudofractal networks to study the relation-ship between enumeration of spanning trees and random walks. We then calculate the enumeration of spanning trees and mean receiving time and see that the mean receiving time increases with the increasing of number of spanning trees, showing that the efficiency of random walks decreases with the number of spanning trees.In Chapter V, we summarize the conclusions and give some further studies in the future.