Expected Value of Zagreb Indices of Random Bipartite Graphs

Document Type : Research Paper


1 Department of Mathematics‎, ‎Science and Research Branch‎, ‎Islamic Azad University‎, ‎Tehran‎, ‎Iran

2 Department of Mathematics‎, ‎Faculty of Mathematical Sciences‎, ‎Tarbiat Modares University‎, ‎Tehran‎, ‎Iran

3 Faculty of Engineering Modern Technologies‎, ‎Amol University of Special Modern Technologies‎, ‎Amol‎, ‎Iran‎


‎In this paper‎, ‎we calculate the expected values of the first and second Zagreb indices‎, ‎denoted as $\textbf{E}\left(M_1\right)$ and $\textbf{E}\left(M_2\right)$ respectively‎, ‎as well as the expected value of the forgotten index‎, ‎$\textbf{E}\left(F\right)$‎, ‎for two models of random bipartite graphs‎. ‎To evaluate our findings‎, ‎we establish the growth rate by demonstrating that for a random bipartite graph $G$ of order $n$ in either model‎, ‎the expected value of $M_1(G)$ is $O\left( n^3 \right)$‎. ‎Furthermore‎, ‎we prove that the expected values of $M_2(G)$ and $F(G)$ are both $O\left( n^4 \right)$‎.


Main Subjects

[1] M. E. J. Newman, S. H. Strogatz and D. J. Watts, Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E 64 (2001) p. 026118.
[2] B. Bollobás, Probabilistic Combinatorics and Its Applications, Providence, American Mathematical Society, 1991.
[3] J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics, 244, Springer, New York, 2008.
[4] P. Erdös and A. Rényi, On random graphs, I, Publ. Math. Debrecen 6 (1959) 290–297.
[5] P. Erdös and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci. 5 (1960) 17–61, https://doi.org/10.1515/9781400841356.38.
[6] Z. Palka, On the degrees of vertices in a bichromatic random graph, Period. Math. Hungar. 15 (1984) 121–126.
[7] F. Skerman, Degree sequences of random bipartite graphs, Ph.D. Thesis, The Australian National University, Canberra, 2010.
[8] B. D. McKay and N. C. Wormald, The degree sequence of a random graph, I, The models, Random Struct. Algorithms 11 (1997) 97–117.
[9] M. Ghorbani and M. A. Hosseinzadeh, A note of Zagreb indices of nanostar dendrimers, Optoelectron. Adv. Mater. Rapid Comm. 4 (2010) 1877–1880.
[10] I. Gutman, B. Furtula and C. Elphick, Three new/old vertex-degree-based topological indices, MATCH Commun. Math. Comput. Chem. 72 (2014) 617–682.
[11] M. A. Hosseinzadeh and M. Ghorbani, On the Zagreb indices of nanostar dendrimers, Optoelectron. Adv. Mater. Rapid Comm. 4 (2010) 378–380.
[12] M. A. Hosseinzadeh and M. Ghorbani, GA index of nanostar dendrimers, J. Optoelectron. Adv. Mater. 11 (2009) 1671–1674.
[13] H. S. Ramane, S. Y. Talwar and I. Gutman, Zagreb indices and coindices of total graph, semi-total point graph and semi-total line graph of subdivision graphs, Math. Interdisc. Res. 5 (2020) 1–12, https://doi.org/10.22052/MIR.2018.134814.1103.
[14] M. Azari, On eccentricity version of Zagreb coindices, Math. Interdisc. Res. 6 (2021) 107– 120, https://doi.org/10.22052/MIR.2021.240325.1247.
[15] B. Liu and Z. You, A survay on comparing Zagreb indices, MATCH Commun. Math. Comput. Chem. 65 (2011) 581–593.
[16] B. Furtula and I. Gutman, A forgotten topological index, J. Math. Chem. 53 (2015) 1184–1190, https://doi.org/10.1007/s10910-015-0480-z.
[17] T. Došlic, M. A. Hosseinzadeh, S. Hossein-Zadeh, A. Iranmanesh and F. Rezakhanlou, On generalized Zagreb indices of random graphs, MATCH Commun. Math. Comput. Chem. 84 (2020) 499–511.
[18] The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.8), 2019, https://www.sagemath.org.
Volume 15, Issue 1
Special Issue Dedicated to the memory of Professor Ali Reza Ashrafi (University of Kashan, I.R. Iran), who was the creator and the Editor-in-Chief of IJMC for 14 years.
March 2024
Pages 27-37