On the Zagreb indices of graphs with given Roman domination number

Document Type : Original paper

Authors

1 MENGGABANG TELIPOT KUALA NERUS

2 Universiti Malaysia Terengganu(UMT), Malaysia

3 Universiti Putra Malaysia(UPM)

Abstract

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. The two Zagreb indices $M_1=\sum_{v\in V(G)} d^2_G(v)$ and $M_2=\sum_{uv\in E(G)} d_G(u)d_G(v)$ are vertex degree based graph invariants that have been introduced in the 1970s and extensively studied ever since. {In this paper, we first give a lower bound on the first Zagreb index of trees with given Roman domination number and we characterize all extremal trees. Then we present upper bound for Zagreb indices of unicyclic and bicyclic graphs with given Roman domination number.

Keywords

Main Subjects

References

[1] A.A.S. Ahmad Jamri, R. Hasni, M.K. Jamil, and D.A. Mojdeh, Maximum second Zagreb index of trees with given Roman domination number, submitted.
[2] S. Bermudo, J.E. Nápoles, and J. Rada, Extremal trees for the Randić index with given domination number, Appl. Math. Comput. 375 (2020), 125122.
[3] B. Borovicanin, K.C. Das, B. Furtula, and I. Gutman, Bounds for zagreb indices, MATCH Commun. Math. Comput. Chem. 78 (2017), no. 1, 17–100.
[4] Bojana Borovićanin and Boris Furtula, On extremal Zagreb indices of trees with given domination number, Appl. Math. Comput. 279 (2016), 208–218.
[5] E.W. Chambers, B. Kinnersley, N. Prince, and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. 23 (2009), no. 3, 1575–1586.
[6] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Roman domination in graphs, Topics in Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer, Berlin/Heidelberg, 2020, pp. 365–409.
[7] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE Int. J. Graphs Comb. 17 (2020), no. 3, 966–984.
[8] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination, Structures of Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer, Berlin/Heidelberg, 2021, pp. 273–307.
[9] E.J. Cockayne, R.M. Dawes, and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980), no. 3, 211–219.
[10] P. Dankelmann, Average distance and domination number, Discrete Appl. Math. 80 (1997), no. 1, 21–35.
[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, submitted.
[12] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Topics in Domination in Graphs, Springer, Berlin/Heidelberg, 2020.
[13] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[14] I. Milovanović, M. Matejić, E. Milovanović, and R. Khoeilar, A note on the first Zagreb index and coindex of graphs, Commun. Comb. Optim. 6 (2021), no. 1, 41–51.
[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.
[16] S. Nikolić, G. Kovačević, A. Miličević, and N. Trinajstić, The Zagreb indices 30 years after, Croat. Chem. Acta 76 (2003), no. 2, 113–124.
[17] D.B. West, Introduction to Graph Theory, Prentice hall Upper Saddle River, New Jersey, 2001.
Communications in Combinatorics and Optimization
Volume 8, Issue 1
March 2023
Pages 141-152

Files

Share

How to cite

Statistics