ON THE COMPLEXITIES OF FAREY GRAPHS

Nithya Sai Narayana

Abstract


Farey Graph is associated with the sequence of irreducible fractions between 0 and 1  called the Farey Sequence and is constructed recursively by adding 2^{n-1} new vertices and 2^n  new edges at every  nth stage starting with K2. Farey Graphs are useful in representing the complex technical, social and biological networks of real world where the growth process depends upon the existing structure in iterative manner. The spanning trees of the graph indicate the connectivity of networks and random walks, dimer covering are some of the areas in which the enumeration of spanning trees are applied. In this paper the recurrence relation satisfied by Farey Graphs are studied and used to enumerate the number of spanning trees of Farey Graphs and some of related graphs. 
Keywords — Farey Graph, Recurrence relation, spanning trees

AMS Subject Classification: 05C05, 05C30, 05C85, 68R05


Full Text:

ijmsc-8-1-04

References


A. Modabish and M.El. Marraki, “The Number of Spanning Trees of Certain Families of Planar Maps “, Applied Mathematical Sciences, Vol. 5, No. 18 (2011), 883 - 898.

Nithya Sai Narayana, “Recurrence relation on the number of spanning trees of generalized book graphs and related family of graphs” , International Journal of Mathematics and Soft Computing,Vol. 6, No.2(2016), pages 75-85, ISSN Print 2249-3328, ISSN Online 2319-5215

Yunhua Liao, Yaoping Hou and Xiaoling Shen, “Tutte polynomial of a small-world Farey graph” , 29 November 2013 ,EPL (Europhysics Letters), Volume 104, Number 3.

Zhongzhi Zhang and Francesc Comellas, “Farey Graphs As Models For Complex Networks”, Theoretical Computer Science, Volume 412,

Issue 8-10, 4 March 2011, Pages 865-875.


Refbacks

  • There are currently no refbacks.




Web Counters

IJMSC has been indexed in several world class data bases like Google Scholar, DRJI (Directory of Research Journals Indexing) ,Cite Factor, Research Bible.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.