Combinatorial properties of Farey graphs (Q2333787)

A Farey graph \(\mathcal F\), is translated from Farey sequences, is a graph with vertex set on irreducible rational numbers between \(0\) and \(1\) and two rational numbers \(\frac{p}{q}\) and \(\frac{r}{s}\) are adjacent in \(\mathcal F\) if and only if \(rq-ps=1\) or \(-1\). Farey graphs are \(3\)-colorable, uniquely Hamiltonian, maximally outerplanar, perfect, modular, have an exponential degree hierarchy, and are also small world, hence are applicable to real networks like social and technical networks. Also, Farey graphs have deterministic character. This article discusses some combinatorial properties of Farey graphs. The dominating number and number of dominating sets are computed and, proved that the number of dominating sets grows exponentially with vertex set. The independence number, maximum independent sets, the number of independent sets, matching number, and number of maximum matchings of Farey graphs are discussed. This paper also establish recursive relations to compute the number of dominating sets, the number of independent sets and the number of maximum matchings of Farey graphs. The asymptotic growth constant of dominating sets, independent sets and matching are also computed. The number of acyclic orientations and root connected orientations in a Farey graph are discussed and studied. This article is worth studying, since the combinatorial properties of Farey graphs are relevant to many practical applications such as network science and graph data mining.