Combinatorial properties of Farey graphs

DOI10.1016/J.TCS.2019.08.022MaRDI QIDQ2333787zbMATH OpenOpenAlexWikidataFDO

Authors Yucheng Wang, Qi Bao, Zhongzhi Zhang

Publication date 13 November 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.08.022

zbMATH Keywords

combinatorial problemdomination numberFarey graphindependence numbermatching numbermaximum independence setmaximum matchingminimum dominating set

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Social networks; opinion dynamics (91D30)

Review text

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.

Recommendations

• Combinatorics of \(k\)-Farey graphs
• Enumerative properties of Ferrers graphs
• The Feller property for graphs
• Combinatorial properties of dependence graphs
• Fubini numbers and polynomials of graphs
• Factorial properties of graphs
• Combinatorial properties of products of graphs
• scientific article; zbMATH DE number 691512
• On the Fibonacci numbers of the composition of graphs
• Combinatorial Relations and Chromatic Graphs

Cites work

• A Contribution to the Theory of Chromatic Polynomials
• Acyclic orientations of graphs
• Algorithms for maximum independent sets
• Automorphisms of the pants complex
• Collective dynamics of `small-world' networks
• Deterministic small-world networks
• Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
• Farey graphs as models for complex networks
• Farey Series and Maximal Outerplanar Graphs
• Geometry of pseudocharacters.
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1369835 (Why is no real title available?)
• Inapproximability of dominating set on power law graphs
• Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
• Matching theory
• Maximum matching in regular and almost regular graphs
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Models of the small world.
• Network science. With Márton Pósfai
• On Dominating Sets and Independent Sets of Graphs
• On Farey table and its compression for space optimization with guaranteed error bounds
• On maximum independent set of categorical product and ultimate categorical ratios of graphs
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• On the number of minimal dominating sets on some graph classes
• On the spectrum of the normalized Laplacian of iterated triangulations of graphs
• Renormalization group analysis of the small-world network model
• Simplicial embeddings between pants graphs
• The asymptotic dimension of a curve graph is finite
• The complexity of computing the permanent
• The Complexity of Enumeration and Reliability Problems
• The Haros-Farey sequence at two hundred years. A survey
• The normalized Laplacian spectrum of subdivisions of a graph
• The small-world phenomenon: an algorithmic perspective
• The Structure and Function of Complex Networks
• Vertex labeling and routing for Farey-type symmetrically-structured graphs

Cited in

(9)

• Ubiquity and the Farey graph
• Combinatorics of \(k\)-Farey graphs
• Rainbow vertex-connection number on a small-world Farey graph
• Farey-subgraphs and continued fractions
• Farey lines defining Farey diagrams and application to some discrete structures
• The Farey graph
• Modeling spatial networks by contact graphs of disk packings
• The Tutte polynomial of a class of compound graphs and its applications
• Farey graphs as models for complex networks

This page was built for publication: Combinatorial properties of Farey graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2333787)