The minimum Zagreb indices for unicyclic graphs with fixed Roman domination number

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, Faculty of Sciences, Golestan University, Gorgan, Iran

2 Special Interest Group on Modelling and Data Analytics (SIGMDA), Faculty of Computer Science and Mathematics, Universiti Malaysia Terengganu, 21030 Kuala Nerus, Terengganu, Malaysia

3 Department of Mathematics, Estahban Branch, Islamic Azad University, Estahban, Iran

4 School of Mathematical Sciences, Universiti Sains Malaysia, 11800 USM Penang, Malaysia

Abstract

Let G=(V,E) be a graph with the vertex set V and the edge set E. The first Zagreb index of a graph G is defined to be the sum of squares of degrees of all the vertices of the graph. The second Zagreb index of the graph G is the sum of the d(u)d(v) for every edge uv∈E, where d(u) and d(v) denote the degree of the vertices u,v∈V. In this paper, we propose new lower bounds of the Zagreb indices of unicyclic graphs in terms of the order and the Roman domination number. We prove that 4n−2(γR−⌈2n3⌉) and 4n−3(γR−⌈2n3⌉) are the sharp lower bounds for the first Zagreb index and the second Zagreb index, respectively. Also, we characterize the extremal trees for these lower bounds.

Keywords

Main Subjects

References

[1] A.A.S. Ahmad Jamri, R. Hasni, M. Kamran Jamil, and D.A. Mojdeh, Maximum second Zagreb index of trees with given Roman domination number, Trans. Comb. 12 (2023), no. 1, 1–10.  https://doi.org/10.22108/toc.2022.128323.1848
[2] A.A.S. Ahmad Jamri, R. Hasni, and S.K. Said Husain, On the Zagreb indices of graphs with given Roman domination number, Commun. Comb. Optim. 8 (2023), no. 1, 141–152. https://doi.org/10.22049/cco.2021.27439.1263
[3] A.A.S. Ahmad Jamri, F. Movahedi, R. Hasni, and M.H. Akhbari, A lower bound for the second Zagreb index of trees with given Roman domination number, Commun. Comb. Optim. 8 (2023), no. 2, 391–396. https://doi.org/10.22049/CCO.2022.27553.1288
[4] A. Ali, K.C. Das, and S. Akhter, On the extremal graphs for second Zagreb index with fixed number of vertices and cyclomatic number, Miskolc Math. Notes 23 (2022), no. 1, 41–50. http://dx.doi.org/10.18514/MMN.2022.2382
[5] A. Behtoei, M. Jannesari, and B. Taeri, Maximum Zagreb index, minimum hyper-Wiener index and graph connectivity, Appl. Math. Lett. 22 (2009), no. 10, 1571–1576. https://doi.org/10.1016/j.aml.2009.05.001
[6] B. Borovićanin and B. Furtula, On extremal Zagreb indices of trees with given domination number, Appl. Math. Comput. 279 (2016), 208–218.  https://doi.org/10.1016/j.amc.2016.01.017
[7] B. Borovićanin, B. Furtula, and I. Gutman, Bounds for Zagreb indices, MATCH Commun. Math. Comput. Chem. 78 (2017), 17–100.
[8] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22.  https://doi.org/10.1016/j.disc.2003.06.004
[9] K.C. Das, I. Gutman, and B. Zhou, New upper bounds on Zagreb indices, J. Math. Chem. 46 (2009), no. 2, 514–521. https://doi.org/10.1007/s10910-008-9475-3
[10] K.C. Das, K. Xu, and J. Nam, Zagreb indices of graphs, Front. Math. China 10 (2015), no. 3, 567–582. https://doi.org/10.1007/s11464-015-0431-9
[11] Z. Du, A.A.S. Ahmad Jamri, R. Hasni, and D.A. Mojdeh, Maximal first Zagreb index of trees with given Roman domination number, AIMS Math. 7 (2022), no. 7, 11801–11812.
[12] I. Gutman and N. Trinajstić, Graph theory and molecular orbitals. Total φ-electron energy of alternant hydrocarbons, Chem. Phys. Lett. 17 (1972), no. 4, 535–538.  https://doi.org/10.1016/0009-2614(72)85099-1
[13] M. Liu and B. Liu, The second Zagreb indices and Wiener polarity indices of trees with given degree sequences, MATCH Commun. Math. Comput. Chem. 67 (2012), no. 2, 439.
[14] M. Liu and B. Liu, The second Zagreb indices of unicyclic graphs with given degree sequences, Discrete Appl. Math. 167 (2014), 217–221.  https://doi.org/10.1016/j.dam.2013.10.033
[15] D.A. Mojdeh, M. Habibi, L. Badakhshian, and Y. Rao, Zagreb indices of trees, unicyclic and bicyclic graphs with given (total) domination, IEEE Access 7 (2019), 94143–94149.  https://doi.org/10.1109/ACCESS.2019.2927288
[16] A. Poureidi, N.A.A. Aziz, N. Jafari Rad, and H. Kamarulhaili, Computing strong Roman domination of trees and unicyclic graphs in linear time, Bull. Malays. Math. Sci. Soc. 45 (2022), no. 5, 2509–2523. https://doi.org/10.1007/s40840-022-01301-4
[17] S.S. Shirkol, P.P. Kumbargoudra, and M.M. Kaliwal, On Roman domination in middle graphs, J. Shanghai Jiaotong Univ. 17 (2021), no. 7, 10–18.
[18] S.D. Stankov, M.M. Matejić, I.Z. Milovanović, E.I. Milovanović, and S.B. Bozkurt Altindağ, Some new bounds on the first Zagreb index, Electron. J. Math. 1 (2021), 101–107.
[19] D. Thakkar and S. Badiyani, Total Roman domination number of graphs, TWMS J. Apl. Eng. Math. 12 (2022), no. 2, 445–455.
[20] D.B. West, Introduction to Graph Theory, Prentice hall Upper Saddle River, 2001.
[21] K. Xu, The Zagreb indices of graphs with a given clique number, Appl. Math. Lett. 24 (2011), no. 6, 1026– 1030. https://doi.org/10.1016/j.aml.2011.01.034
[22] Z. Yan, H. Liu, and H. Liu, Sharp bounds for the second Zagreb index of unicyclic graphs, J. Math. Chem. 42 (2007), no. 3, 565–574.  https://doi.org/10.1007/s10910-006-9132-7
[23] B. Zhou, Zagreb indices, MATCH Commun. Math. Comput. Chem 52 (2004), no. 1, 113–118.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 30 November 2024

Files

Share

How to cite

Statistics