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.
Download full-text PDF |
Source |
|---|---|
| http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4863731 | PMC |
| http://dx.doi.org/10.1038/srep25621 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
On Nordhaus-Gaddum type relations of -complement graphs.
Heliyon
June 2023
Department of Mathematics, Faculty of Science, Mahasarakham University, Maha Sarakham 44150, Thailand.
The -complement graphs were introduced by Amrithalakshmi et al. in 2022. In their work, some interesting properties of the graphs such as -self-complementary, adjacency, and hamiltonicity were studied.
View Article and Find Full Text PDFGeometry, number theory, and the butterfly spectrum of two-dimensional Bloch electrons.
Phys Rev E
October 2021
Department of Physics and Astronomy, George Mason University, Fairfax, Virginia 22030, USA.
We take a deeper dive into the geometry and the number theory that underlay the butterfly graphs of the Harper and the generalized Harper models of Bloch electrons in a magnetic field. The root of the number theoretical characteristics of the fractal spectrum is traced to a close relationship between the Farey tree-the hierarchical tree that generates all rationals and the Wannier diagram-a graph that labels all the gaps of the butterfly graph. The resulting Farey-Wannier hierarchical lattice of trapezoids provides a geometrical representation of the nested pattern of butterflies in the butterfly graph.
View Article and Find Full Text PDFRenormalization group for link percolation on planar hyperbolic manifolds.
Phys Rev E
August 2019
School of Mathematical Sciences, Queen Mary University of London, London, E1 4NS, United Kingdom and Alan Turing Institute, 96 Euston Rd, London, NW1 2DB, United Kingdom.
Network geometry is currently a topic of growing scientific interest, as it opens the possibility to explore and interpret the interplay between structure and dynamics of complex networks using geometrical arguments. However, the field is still in its infancy. In this work we investigate the role of network geometry in determining the nature of the percolation transition in planar hyperbolic manifolds.
View Article and Find Full Text PDFStructure Properties of Generalized Farey graphs based on Dynamical Systems for Networks.
Sci Rep
August 2018
System and Network Engineering research group, Informatics Institute, University of Amsterdam, Science Park 904, 1098XH, Amsterdam, The Netherlands.
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.
View Article and Find Full Text PDFLabel-based routing for a family of small-world Farey graphs.
Sci Rep
May 2016
School of Automation, Guangdong University of Technology, Guangzhou, 510006, China.
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).
View Article and Find Full Text PDFWant AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!