Name
Abstract | ||
|---|---|---|
Combinatorial problems are a fundamental research subject of theoretical computer science, and for a general graph many combinatorial problems are NP-hard and even #P-complete. Thus, it is interesting to seek or design special graphs for which these difficult combinatorial problems can be exactly solved. In this paper, we study some combinatorial problems for the Farey graphs, which are translated from Farey sequences and have received considerable attention from the scientific community. We determine exactly the domination number, the independence number, and the matching number. Moreover, we derive exact or recursive solutions to the number of minimum dominating sets, the number of dominating sets, the number of maximum independent sets, the number of independent sets, the number of maximum matchings, as well as the number of matchings. Finally, we obtain explicit expressions for the number of acyclic orientations and the number of root-connected acyclic orientations. Since the considered combinatorial problems have found wide applications in diverse fields, such as network science and graph data miming, this work is helpful for deepening our understanding of the applications for these combinatorial problems. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.tcs.2019.08.022 | Theoretical Computer Science |
Keywords | Field | DocType |
Farey graph,Combinatorial problem,Minimum dominating set,Maximum independence set,Maximum matching,Domination number,Independence number,Matching number | Network science,Graph,Discrete mathematics,Combinatorics,Independence number,Expression (mathematics),Domination analysis,Recursion,Farey sequence,Mathematics | Journal |
Volume | ISSN | Citations |
796 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yucheng Wang | 1 | 0 | 0.34 |
| Qi Bao | 2 | 1 | 1.36 |
| Zhongzhi Zhang | 3 | 85 | 22.02 |