Research ArticleNo Access

On maximum Zagreb indices of bipartite graphs with a given connectivity

Hanlin Chen

https://orcid.org/0000-0003-3692-5411

College of Computer Engineering and Applied Mathematics, Changsha University, Changsha 410022, P. R. China

E-mail Address: hlchen@ccsu.edu.cn

Corresponding author.

Search for more papers by this author

and

Qiuzhi Guo

College of Financial Mathematics and Statistics, Guangdong University of Finance, Guangzhou 510521, P. R. China

Search for more papers by this author

https://doi.org/10.1142/S1793557123500389Cited by:0 (Source: Crossref)

Abstract

For a graph, the first (multiplicative) Zagreb index is equal to the sum (product) of squares of the vertex degrees, and the second (multiplicative) Zagreb index is equal to the sum (product) of products of the degrees of a pair of adjacent vertices. In this work, by a unified approach, we determine the extremal values of these Zagreb indices in terms of the (edge) connectivity and characterize the corresponding extremal graphs among all connected bipartite graphs of order $n$ . Our results show that the extremal graphs of given (edge) connectivity regarding the Zagreb indices and multiplicative Zagreb indices do not completely coincide with other topological indices.

Communicated by I. Peterin

Keywords:

AMSC: 05C09, 05C92, 05C50

References

1. B. Bollobás , Modern Graph Theory (Springer-Verlag, 1998). Crossref, Google Scholar
2. B. Borovicanin, K. C. Das, B. Furtula and I. Gutman , Bounds for Zagreb indices, MATCH Commun. Math. Comput. Chem. 78 (2017) 17–100. Web of Science, Google Scholar
3. É. Bonnet, B. Escoffier, V. T. Paschos and G. Stamoulis , Purely combinatorial approximation algorithms for maximum $k$ -vertex cover in bipartite graphs, Discrete Optim. 27 (2017) 26–56. Crossref, Web of Science, Google Scholar
4. G. Berkolaiko, J. B. Kennedy, P. Kurasov and D. Mugnolo , Edge connectivity and the spectral gap of combinatorial and quantum graphs, J. Phys. A: Math. Theor. 50 (2017) 365201. Crossref, Web of Science, Google Scholar
5. V. Božović, T. K. VukiScević and G. Popivoda , Chemical trees with extreme values of a few types of multiplicative Zagreb indices, MATCH Commun. Math. Comput. Chem. 76 (2016) 207–220. Web of Science, Google Scholar
6. H. Chen and H. Deng , Extremal bipartite graphs of given connectivity with respect to matching energy, Discrete Appl. Math. 239 (2018) 200–205. Crossref, Web of Science, Google Scholar
7. H. Chen, R. Wu and H. Deng , The extremal values of some topological indices in bipartite graphs with a given matching number, Appl. Math. Comput. 280 (2016) 103–109. Web of Science, Google Scholar
8. H. Chen, R. Wu and H. Deng , The extremal values of some monotonic topological indices in graphs with a given vertex bipartiteness, MATCH Commun. Math. Comput. Chem. 78 (2017) 103–120. Web of Science, Google Scholar
9. T. C. E. Cheng, Y. Guo, S. Zhang and Y. Du , Extreme values of the sum of squares of degrees of bipartite graphs, Discrete Math. 309 (2009) 1557–1564. Crossref, Web of Science, Google Scholar
10. Y. Cui and X. Wang , Detecting one-mode communities in bipartite networks by bipartite clustering triangular, Physica A 457 (2016) 307–315. Crossref, Web of Science, Google Scholar
11. H. Deng , A unified approach to the extremal Zagreb indices for trees, unicyclic graphs and bicyclic graphs, MATCH Commun. Math. Comput. Chem. 57 (2007) 597–616. Web of Science, Google Scholar
12. L. Feng and A. Ilić , Zagreb, Harary and hyper-Wiener indices of graphs with a given matching number, Appl. Math. Lett. 23 (2010) 943–948. Crossref, Web of Science, Google Scholar
13. I. Gutman and K. C. Das , The first Zagreb indices 30 years after, MATCH Commun. Math. Comput. Chem. 50 (2004) 103–112. Google Scholar
14. I. Gutman, B. Ruščić, N. Trinajstić and C. F. Wilcox , Graph theory and molecular orbitals. XII. Acyclic polyenes, J. Chem. Phys. 62 (1975) 3399–3405. Crossref, Web of Science, Google Scholar
15. I. Gutman and N. Triajstić , Graph theory and molecular orbitals. III. Total $π$ -electron energy of alternant hydrocarbons, Chem. Phys. Lett. 17 (1972) 535–538. Crossref, Web of Science, Google Scholar
16. I. Gutman and S. Zhang , Graph connectivity and Wiener index, Bull. Acad. Serbe Sci. Arts Cl. Math. Nat. 133 (2006) 1–5. Google Scholar
17. Y. Guo, Y. Du and W. Ying , Bipartite graphs with extreme values of the first general zagreb index, MATCH Commun. Math. Comput. Chem. 63 (2010) 469–480. Web of Science, Google Scholar
18. M. Han, X. Yuan and J. Li , A note on Laplacian spectral radius of bipartite graphs with given connectivity, Adv. Math. 5 (2014) 209–223. Google Scholar
19. S. Koichi et al., Chemical structure elucidation from $^{13} C$ NMR chemical shifts: efficient data processing using bipartite matching and maximal clique algorithms, J. Chem. Inf. Model. 54 (2014) 1027–1035. Crossref, Web of Science, Google Scholar
20. J. Li, W. Shiu and W. Chan , The Laplacian spectral radius of some graphs, Linear Algebra Appl. 431(1) (2009) 99–103. Crossref, Web of Science, Google Scholar
21. P. G. Lind, M. C. González and H. J. Herrmann , Cycles and clustering in bipartite networks, Phys. Rev. E 72 (2005) 056127. Crossref, Web of Science, Google Scholar
22. R. Lang, X. Deng and H. Lu , Bipartite graphs with the maximal value of the second Zagreb index, B. Malays. Math. So. 1 (2013) 1–6. Google Scholar
23. S. Li and Y. Song , On the sum of all distances in bipartite graphs, Discrete Appl. Math. 169 (2014) 176–185. Crossref, Web of Science, Google Scholar
24. S. Li, Y. Wu and L. Sun , On the minimum eccentric distance sum of bipartite graphs with some given parameters, J. Math. Anal. Appl. 430 (2015) 1149–1162. Crossref, Web of Science, Google Scholar
25. S. Li and H. Zhou , On the maximum and minimum Zagreb indices of graphs with connectivity at most $k$ , Appl. Math. Lett. 23 (2010) 128–132. Crossref, Web of Science, Google Scholar
26. S. Li and M. Zhang , Sharp upper bounds for Zagreb indices of bipartite graphs with a given diameter, Appl. Math. Lett. 24 (2011) 131–137. Crossref, Web of Science, Google Scholar
27. A. Niu, D. Fan and G. Wang , On the distance Laplacian spectral radius of bipartite graphs, Discrete Appl. Math. 186 (2015) 207–213. Crossref, Web of Science, Google Scholar
28. A. Niu, G. Wang and D. Fan , Correction to On the distance Laplacian spectral radius of bipartite graphs [Discrete Appl. Math. 186 (2015) 207–213.], Discrete Appl. Math. 208 (2016) 137–140. Crossref, Web of Science, Google Scholar
29. M. Nath and S. Paul , On the distance spectral radius of bipartite graphs, Linear Algebra Appl. 436 (2012) 1285–1296. Crossref, Web of Science, Google Scholar
30. Y. Mao, Z. Wang and Y. Xiao , Steiner Wiener index and connectivity of graphs, Utilitas Mathematica 102 (2017) 51–57. Web of Science, Google Scholar
31. S. Qiao , On zeroth-order general Randić index of quasi-tree graphs containing cycles, Discrete Optim. 7 (2010) 93–98. Crossref, Web of Science, Google Scholar
32. S. Aslan and M. Kaya , Link prediction methods in bipartite networks, Proc. Int. Conf. Comput. Sci. Eng. (2017) 1095–1099. Crossref, Google Scholar
33. Y. Sun , On the maximum and minimum sizes of a graph with given $k$ -connectivity, Discuss. Math. Graph T 37 (2016) 623–632. Crossref, Web of Science, Google Scholar
34. K. Takazawa , Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs, Discrete Optim. 26 (2017) 26–40. Crossref, Web of Science, Google Scholar
35. R. Todeschini, D. Ballabio and V. Consonni , Novel molecular descriptors based on functions of the vertex degrees, in Novel Molecular Structure Descriptors-Theorty and Applicatons I, eds. I. Gutman and B. Furtula (Kragujevac, 2010), pp. 73–100. Google Scholar
36. R. Todeschini and V. Consonni , New local vertex invariants and molecular descriptors based on functins of the vertex degrees, MATCH Commun. Math. Comput. Chem. 68 (2010) 359–372. Google Scholar
37. Ž. K. Vukićević and G. Popivoda , Chemical trees with extreme values of Zagreb indices and coindices, Iran. J. Math. Chem. 5 (2014) 19–29. Google Scholar
38. C. Wang, J. Liu and S. Wang , Sharp upper bounds for multiplicative Zagreb indices of bipartite graphs with given diameter, Discrete Appl. Math. 227 (2017) 156–165. Crossref, Web of Science, Google Scholar
39. R. Wu, H. Chen and H. Deng , On the monotonicity of topological indices and the connectivity of a graph, Appl. Math. Comput. 298 (2017) 188–200. Web of Science, Google Scholar
40. K. Xu and H. Hua , A unified approach to extremal multiplicative Zagreb indices for trees, unicyclic and bicyclic graphs, MATCH Commun. Math. Comput. Chem. 68 (2012) 241–256. Web of Science, Google Scholar
41. P. Zhang et al., Clustering coefficient and community structure of bipartite networks, Physica A 387 (2008) 6869–6875. Crossref, Web of Science, Google Scholar
42. T. Zhou, J. Ren, M. Medo and Y. Zhang , Bipartite network projection and personal recommendation, Phys. Rev. E 76 (2007) 046115. Crossref, Web of Science, Google Scholar