Combinatorial properties of Farey graphs (Q2333787)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Combinatorial properties of Farey graphs
scientific article

    Statements

    Combinatorial properties of Farey graphs (English)
    0 references
    0 references
    0 references
    0 references
    13 November 2019
    0 references
    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.
    0 references
    0 references
    Farey graph
    0 references
    combinatorial problem
    0 references
    minimum dominating set
    0 references
    maximum independence set
    0 references
    maximum matching
    0 references
    domination number
    0 references
    independence number
    0 references
    matching number
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references