Structure Properties of Generalized Farey graphs based on Dynamical Systems for Networks.

Farey graphs are simultaneously small-world, uniquely Hamiltonian, minimally 3-colorable, maximally outerplanar and perfect. Farey graphs are therefore famous in deterministic models for complex networks. By lacking of the most important characteristics of scale-free, Farey graphs are not a good model for networks associated with some empirical complex systems. We discuss here a category of graphs which are extension of the well-known Farey graphs. These new models are named generalized Farey graphs here. We focus on the analysis of the topological characteristics of the new models and deduce the complicated and graceful analytical results from the growth mechanism used in generalized Farey graphs. The conclusions show that the new models not only possess the properties of being small-world and highly clustered, but also possess the quality of being scale-free. We also find that it is precisely because of the exponential increase of nodes' degrees in generalized Farey graphs as they grow that caused the new networks to have scale-free characteristics. In contrast, the linear incrementation of nodes' degrees in Farey graphs can only cause an exponential degree distribution.

Label-based routing for a family of small-world Farey graphs.

We introduce an informative labelling method for vertices in a family of Farey graphs, and deduce a routing algorithm on all the shortest paths between any two vertices in Farey graphs. The label of a vertex is composed of the precise locating position in graphs and the exact time linking to graphs. All the shortest paths routing between any pair of vertices, which number is exactly the product of two Fibonacci numbers, are determined only by their labels, and the time complexity of the algorithm is O(n). It is the first algorithm to figure out all the shortest paths between any pair of vertices in a kind of deterministic graphs. For Farey networks, the existence of an efficient routing protocol is of interest to design practical communication algorithms in relation to dynamical processes (including synchronization and structural controllability) and also to understand the underlying mechanisms that have shaped their particular structure.