Wang, Yucheng; Bao, Qi; Zhang, Zhongzhi Combinatorial properties of Farey graphs. (English) Zbl 1444.05112 Theor. Comput. Sci. 796, 70-89 (2019). 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. Reviewer: K. A. Germina (Kerala) Cited in 2 Documents MSC: 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C35 Extremal problems in graph theory 05C30 Enumeration in graph theory 05C45 Eulerian and Hamiltonian graphs 05C82 Small world graphs, complex networks (graph-theoretic aspects) 91D30 Social networks; opinion dynamics Keywords:Farey graph; combinatorial problem; minimum dominating set; maximum independence set; maximum matching; domination number; independence number; matching number PDFBibTeX XMLCite \textit{Y. Wang} et al., Theor. Comput. Sci. 796, 70--89 (2019; Zbl 1444.05112) Full Text: DOI References: [1] Barabási, A.-L., Network Science (2016), Cambridge University Press [2] Newman, M. E.J., The structure and function of complex networks, SIAM Rev., 45, 167-256 (2003) · Zbl 1029.68010 [3] Watts, D.; Strogatz, S., Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139 [4] Barahona, M.; Pecora, L. M., Synchronization in small-world systems, Phys. Rev. Lett., 89, Article 054101 pp. (2002) [5] Olfati-Saber, R., Ultrafast consensus in small-world networks, (Proc. 2005 Amer. Control Conf. (2005)), 2371-2378 [6] Tahbaz-Salehi, A.; Jadbabaie, A., Small world phenomenon, rapidly mixing Markov chains, and average consensus algorithms, (Proc. 46th 2007 IEEE Conf. Decision Control (2007)), 276-281 [7] Newman, M. E., Models of the small world, J. Stat. Phys., 101, 819-841 (2000) · Zbl 1049.82520 [8] Newman, M. E.J.; Watts, D. J., Renormalization group analysis of the small-world network model, Phys. Lett. A, 263, 341-346 (1999) · Zbl 0940.82029 [9] Kleinberg, J. M., Navigation in a small world, Nature, 406, 845 (2000) [10] Kleinberg, J. M., The small-world phenomenon: an algorithm perspective, (Proc. 32nd 2000 ACM Symp. Theory of Computing (2000)), 163-170 · Zbl 1296.05181 [11] Comellas, F.; Sampels, M., Deterministic small-world networks, Physica A, 309, 231-235 (2002) · Zbl 0995.60103 [12] Colbourn, C. J., Farey series and maximal outerplanar graphs, SIAM J. Algebraic Discrete Methods, 3, 187-189 (1982) · Zbl 0499.05025 [13] Hardy, G. H.; Wright, E. M., An Introduction to the Theory of Numbers (1979), Oxford University Press · Zbl 0423.10001 [14] Cobeli, C.; Zaharescu, A., The Haros-Farey sequence at two hundred years, Acta Univ. Apulensis, Mat.-Inform., 5, 1-38 (2003) · Zbl 1096.11005 [15] Paria, B.; Pratihar, S.; Bhowmick, P., On Farey table and its compression for space optimization with guaranteed error bounds, Math. Appl., 5, 123-145 (2016) · Zbl 1375.94093 [16] Manning, J. F., Geometry of pseudocharacters, Geom. Topol., 9, 1147-1185 (2005) · Zbl 1083.20038 [17] Bell, G. C.; Fujiwara, K., The asymptotic dimension of a curve graph is finite, J. Lond. Math. Soc., 77, 33-50 (2008) · Zbl 1135.57010 [18] Margalit, D., Automorphisms of the pants complex, Duke Math. J., 121, 457-479 (2004) · Zbl 1055.57024 [19] Aramayona, J., Simplicial embeddings between pants graphs, Geom. Dedic., 144, 115-128 (2010) · Zbl 1194.57020 [20] Xie, P.; Zhang, Z.; Comellas, F., On the spectrum of the normalized Laplacian of iterated triangulations of graphs, Appl. Math. Comput., 273, 1123-1129 (2016) · Zbl 1410.05143 [21] Shan, L.; Li, H.; Zhang, Z., Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph, Theor. Comput. Sci., 677, 12-30 (2017) · Zbl 1369.05164 [22] Shan, L.; Li, H.; Zhang, Z., Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket, Theor. Comput. Sci., 720, 47-54 (2018) · Zbl 1390.05177 [23] Zhang, Z.; Comellas, F., Farey graphs as models for complex networks, Theor. Comput. Sci., 412, 865-875 (2011) · Zbl 1206.68245 [24] Boettcher, S.; Singh, V.; Ziff, R. M., Ordinary percolation with discontinuous transitions, Nat. Commun., 3, 787 (2012) [25] Yi, Y.; Zhang, Z.; Lin, Y.; Chen, G., Small-world topology can significantly improve the performance of noisy consensus in a complex network, Comput. J., 58, 3242-3254 (2015) [26] Zhang, Z.; Wu, B.; Lin, Y., Counting spanning trees in a small-world Farey graph, Physica A, 391, 3342-3349 (2012) [27] Liao, Y.; Hou, Y.; Shen, X., Tutte polynomial of a small-world Farey graph, Europhys. Lett., 104, Article 38001 pp. (2013) [28] Zhai, Y.; Wang, Y., Label-based routing for a family of small-world Farey graphs, Sci. Rep., 6, Article 25621 pp. (2016) [29] Jiang, W.; Zhai, Y.; Martin, P.; Zhao, Z., Structure properties of generalized Farey graphs based on dynamical systems for networks, Sci. Rep., 8, Article 12194 pp. (2018) [30] Jiang, W.; Zhai, Y.; Zhuang, Z.; Martin, P.; Zhao, Z.; Liu, J.-B., Vertex labeling and routing for Farey-type symmetrically-structured graphs, Symmetry, 10, 407 (2018) · Zbl 1423.05145 [31] Nogawa, T.; Hasegawa, T.; Nemoto, K., Criticality governed by the stable renormalization fixed point of the Ising model in the hierarchical small-world network, Phys. Rev. E, 86, Article 030102 pp. (2012) [32] Yuster, R., Maximum matching in regular and almost regular graphs, Algorithmica, 66, 87-92 (2013) · Zbl 1263.05081 [33] Hon, W.-K.; Kloks, T.; Liu, C.-H.; Liu, H.-H.; Poon, S.-H.; Wang, Y.-L., On maximum independent set of categorical product and ultimate categorical ratios of graphs, Theor. Comput. Sci., 588, 81-95 (2015) · Zbl 1326.05106 [34] Chuzhoy, J.; Ene, A., On approximating maximum independent set of rectangles, (Proceedings of IEEE 2016 Annual Symposium on Foundations of Computer Science (2016), IEEE), 820-829 [35] Xie, P.; Zhang, Z.; Comellas, F., The normalized Laplacian spectrum of subdivisions of a graph, Appl. Math. Comput., 286, 250-256 (2016) · Zbl 1410.05144 [36] Gast, M.; Hauptmann, M.; Karpinski, M., Inapproximability of dominating set on power law graphs, Theor. Comput. Sci., 562, 436-452 (2015) · Zbl 1305.05174 [37] Couturier, J.-F.; Letourneur, R.; Liedloff, M., On the number of minimal dominating sets on some graph classes, Theor. Comput. Sci., 562, 634-642 (2015) · Zbl 1305.05219 [38] Robson, J. M., Algorithms for maximum independent sets, J. Algorithms, 7, 425-440 (1986) · Zbl 0637.68080 [39] Halldórsson, M. M.; Radhakrishnan, J., Greed is good: approximating independent sets in sparse and bounded-degree graphs, Algorithmica, 18, 145-163 (1997) · Zbl 0866.68077 [40] Haynes, T. W.; Hedetniemi, S.; Slater, P., Fundamentals of Domination in Graphs (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0890.05002 [41] Valiant, L., The complexity of computing the permanent, Theor. Comput. Sci., 8, 189-201 (1979) · Zbl 0415.68008 [42] Valiant, L., The complexity of enumeration and reliability problems, SIAM J. Comput., 8, 410-421 (1979) · Zbl 0419.68082 [43] Lovász, L.; Plummer, M. D., Matching Theory, Annals of Discrete Mathematics, vol. 29 (1986), North Holland: North Holland New York · Zbl 0618.05001 [44] Liu, Y.-Y.; Slotine, J.-J.; Barabási, A.-L., Controllability of complex networks, Nature, 473, 167-173 (2011) [45] Nacher, J. C.; Akutsu, T., Dominating scale-free networks with variable scaling exponent: heterogeneous networks are not difficult to control, New J. Phys., 14, Article 073005 pp. (2012) [46] Liu, Y. Y.; Barabási, A.-L., Control principles of complex systems, Rev. Mod. Phys., 88, Article 035006 pp. (2016) [47] Liu, Y.; Lu, J.; Yang, H.; Xiao, X.; Wei, Z., Towards maximum independent sets on massive graphs, Proceedings of the 2015 International Conference on Very Large Data Base, 8, 2122-2133 (2015) [48] Chang, L.; Li, W.; Zhang, W., Computing a near-maximum independent set in linear time by reducing-peeling, (Proceedings of the 2017 ACM International Conference on Management of Data (2017), ACM), 1181-1196 [49] González, D. L.; Piro, O., Symmetric kicked self-oscillators: iterated maps, strange attractors, and symmetry of the phase-locking Farey hierarchy, Phys. Rev. Lett., 55, 17 (1985) [50] Kim, S.-H.; Ostlund, S., Simultaneous rational approximations in the study of dynamical systems, Phys. Rev. A, 34, 3426 (1986) [51] Harant, J.; Pruchnewski, A.; Voigt, M., On dominating sets and independent sets of graphs, Comb. Probab. Comput., 8, 547-553 (1999) · Zbl 0959.05080 [52] Wu, W.; Du, H.; Jia, X.; Li, Y.; Huang, S. C.-H., Minimum connected dominating sets and maximal independent sets in unit disk graphs, Theor. Comput. Sci., 352, 1-7 (2006) · Zbl 1086.68107 [53] Stanley, R. P., Acyclic orientations of graphs, Discrete Math., 5, 171-178 (1973) · Zbl 0258.05113 [54] Greene, C.; Zaslavsky, T., On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs, Trans. Am. Math. Soc., 280, 97-126 (1983) · Zbl 0539.05024 [55] Tutte, W. T., A contribution to the theory of chromatic polynomials, Can. J. Math., 6, 3-4 (1954) · Zbl 0055.17101 [56] Welsh, D., The Tutte polynomial, Random Struct. Algorithms, 15, 210-228 (1999) · Zbl 0934.05057 [57] Biggs, N., Algebraic Graph Theory (1993), Cambridge University Press: Cambridge University Press Cambridge This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.