The cyclomatic number, denoted by $ \gamma $, of a graph $ G $ is the minimum number of edges of $ G $ whose removal makes $ G $ acyclic. Let $ \mathscr{G}_{n}^{\gamma} $ be the class of all connected graphs with order $ n $ and cyclomatic number $ \gamma $. In this paper, we characterized the graphs in $ \mathscr{G}_{n}^{\gamma} $ with minimum general Randić index for $ \gamma\geq 3 $ and $ 1\leq\alpha\leq \frac{39}{25} $. These extend the main result proved by A. Ali, K. C. Das and S. Akhter in 2022. The elements of $ \mathscr{G}_{n}^{\gamma} $ with maximum general Randić index were also completely determined for $ \gamma\geq 3 $ and $ \alpha\geq 1 $.
Citation: Guifu Su, Yue Wu, Xiaowen Qin, Junfeng Du, Weili Guo, Zhenghang Zhang, Lifei Song. Sharp bounds for the general Randić index of graphs with fixed number of vertices and cyclomatic number[J]. AIMS Mathematics, 2023, 8(12): 29352-29367. doi: 10.3934/math.20231502
The cyclomatic number, denoted by $ \gamma $, of a graph $ G $ is the minimum number of edges of $ G $ whose removal makes $ G $ acyclic. Let $ \mathscr{G}_{n}^{\gamma} $ be the class of all connected graphs with order $ n $ and cyclomatic number $ \gamma $. In this paper, we characterized the graphs in $ \mathscr{G}_{n}^{\gamma} $ with minimum general Randić index for $ \gamma\geq 3 $ and $ 1\leq\alpha\leq \frac{39}{25} $. These extend the main result proved by A. Ali, K. C. Das and S. Akhter in 2022. The elements of $ \mathscr{G}_{n}^{\gamma} $ with maximum general Randić index were also completely determined for $ \gamma\geq 3 $ and $ \alpha\geq 1 $.
| [1] |
D. Amic, D. Lucic, S. Nikolic, N. Trinajstić, The vertex-connectivity index revisited, J. Chem. Inf. Comput. Sci., 38 (1998), 819–822. https://doi.org/10.1021/ci980039b doi: 10.1021/ci980039b
|
| [2] |
A. Ali, K. C. Das, S. Akhter, On the extremal graphs for second Zagreb index with fixed number of vertices and cyclomatic number, Miskolc Math. Notes, 23 (2022), 41–50. http://doi.org/10.18514/MMN.2022.2382 doi: 10.18514/MMN.2022.2382
|
| [3] |
M. R. Alfuraidan, K. C. Das, T. Vetrík, S. Balachandran, General Randić index of unicyclic graphs with given diameter, Discrete Appl. Math., 306 (2022), 7–16. https://doi.org/10.1016/j.dam.2021.09.016 doi: 10.1016/j.dam.2021.09.016
|
| [4] | J. A. Bondy, U. S. R. Murty, Graph Theory, Berlin: Springer, 2008. |
| [5] | B. Bollobás, P. Erdös, Graphs of extremal weights, Ars Combin., 50 (1998), 225–233. |
| [6] |
D. Chen, Study of unicyclic graph with maximal general Randić index for $\alpha<0$, Commun. Comput. Inf. Sci., 134 (2011), 136–141. https://doi.org/10.1007/978-3-642-18129-022 doi: 10.1007/978-3-642-18129-022
|
| [7] |
Q. Cui, L. Zhong, The general Randić index of trees with given number of pendent vertices, Appl. Math. Comput., 302 (2017), 111–121. https://doi.org/10.1016/j.amc.2017.01.021 doi: 10.1016/j.amc.2017.01.021
|
| [8] |
I. Gutman, N. Trinajstić, Graph theory and molecular orbitals. Ⅲ. Total $\pi$-electron energy of alternant hydrocarbons, Chem. Phys., 17 (1972), 535–538. https://doi.org/10.1016/0009-2614(72)85099-1 doi: 10.1016/0009-2614(72)85099-1
|
| [9] |
L. Buyantogtokh, B. Horoldgva, K. Das, On general reduced second Zagreb index of graphs, Mathematics, 10 (2022), 3553. https://doi.org/10.3390/math10193553 doi: 10.3390/math10193553
|
| [10] | X. Li, Y. Shi, T. Xu, Unicyclic graphs with maximum general Randić index for $\alpha>0$, MATCH Commun. Math. Comput. Chem., 56 (2006), 557–570. |
| [11] | X. Li, L. Wang, Y. Zhang, Complete solution for unicyclic graphs with minimum general Randić index, MATCH Commun. Math. Comput. Chem., 55 (2006), 391–408. |
| [12] | K. Xu, K. C. Das, S. Balachandran, Maximizing the Zagreb indices of $(n, m)$-graphs, MATCH Commun. Math. Comput. Chem., 72 (2014), 641–654. |
| [13] | B. Wu, L. Zhang, Unicyclic graphs with minimum general Randić index, MATCH Commun. Math. Comput. Chem., 54 (2005), 455–464. |
| [14] | M. K. Jamil, I. Tomescu, Zeroth-order general Randić index of $k$-generalized quasi trees, preprint paper, 2018. https://doi.org/10.48550/arXiv.1801.03885 |
Figures(11)
Guifu Su, Yue Wu, Xiaowen Qin, Junfeng Du, Weili Guo, Zhenghang Zhang, Lifei Song. Sharp bounds for the general Randić index of graphs with fixed number of vertices and cyclomatic number[J]. AIMS Mathematics, 2023, 8(12): 29352-29367. doi: 10.3934/math.20231502
DownLoad: