Comparing the Zagreb indices of the NEPS of graphs. (English) Zbl 1287.05025
Summary: The first and the second Zagreb indices of a graph \(G=(V,E)\) are defined as \(M_1(G)=\sum_{u\in V}d_{G}(u)^2\) and \(M_2(G)=\sum uv\in Ed_{G}(u)d_{G}(v)\), where \(d_{G}(u)\) denotes the degree of a vertex \(u\) in \(G\). It has recently been conjectured that \(M_1(G)/|V|\leq M_2(G)/|E|\). Although some counterexamples have already been found, the question of characterizing graphs for which the inequality holds is left open. We show that this inequality is preserved under the NEPS of graphs, while its opposite is preserved under the direct product of graphs.
Keywords:
first Zagreb index; second Zagreb index; Hansen-Vukičević conjecture; NEPS of graphs; Cartesian product of graphs; direct product of graphsReferences:
| [1] | Gutman, I.; Trinajstić, N.; theory, Graph; orbitals, molecular, Total \(\pi \)-electron energy of alternant hydrocarbons, Chem. Phys. Lett., 17, 535-538 (1972) |
| [2] | Nikolić, S.; Kovačević, G.; Milićević, A.; Trinajstić, N., The Zagreb indices 30 years after, Croat. Chem. Acta, 73, 113-124 (2003) |
| [3] | Gutman, I.; Das, K. C., The first Zagreb index 30 years after, MATCH Commun. Math. Comput. Chem., 50, 83-92 (2004) · Zbl 1053.05115 |
| [4] | Xu, K., The Zagreb indices of graphs with a given clique number, Appl. Math. Lett., 24, 1026-1030 (2011) · Zbl 1216.05041 |
| [5] | Andova, V.; Bogoev, S.; Dimitrov, D.; Pilipczuk, M.; Škrekovski, R., On the Zagreb index inequality of graphs with prescribed vertex degrees, Discrete Appl. Math., 159, 852-858 (2011) · Zbl 1222.05028 |
| [6] | Shuchao, L.; Zhang, M., Sharp upper bounds for Zagreb indices of bipartite graphs with a given diameter, Appl. Math. Lett., 24, 131-137 (2011) · Zbl 1223.05052 |
| [7] | Fath-Tabar, G. H., Old and new Zagreb index, MATCH Commun. Math. Comput. Chem., 65, 79-84 (2011) · Zbl 1265.05146 |
| [8] | Su, G.; Xiong, L.; Xu, L.; Ma, B., On the maximum and minimum first reformulated Zagreb index of graphs with connectivity at most k FILOMAT, 25, 4, 75-83 (2011) · Zbl 1265.05127 |
| [9] | P.S. Ranjinia, V. Lokeshab, I.N. Cangülc, On the Zagreb indices of the line graphs of the subdivision graphs, Appl. Math. Comput. http://dx.doi.org/10.1016/j.amc.2011.03.125; P.S. Ranjinia, V. Lokeshab, I.N. Cangülc, On the Zagreb indices of the line graphs of the subdivision graphs, Appl. Math. Comput. http://dx.doi.org/10.1016/j.amc.2011.03.125 · Zbl 1233.05092 |
| [10] | Stevanović, S., On a relation between the Zagreb indices, Croat. Chem. Acta., 84, 17-19 (2011) |
| [11] | Aouchiche, M.; Bonnefoy, J. M.; Fidahoussen, A.; Caporossi, G.; Hansen, P.; Hiesse, L.; Lacheré, J.; Monhait, A., Variable neighborhood search for extremal graphs, (Liberti, L.; Maculan, N., Global Optimization: From Theory to Implementation (2005), Springer), vol. 14 · Zbl 1100.90052 |
| [12] | Hansen, P.; Vukičević, D., Comparing the Zagreb indices, Croat. Chem. Acta, 80, 165-168 (2007) |
| [13] | Vukičević, D.; Graovac, A., Comparing Zagreb \(M_1\) and \(M_2\) indices for acyclic molecules, MATCH Commun. Math. Comput. Chem., 57, 587-590 (2007) · Zbl 1142.05313 |
| [14] | B. Liu, On a conjecture about comparing Zagreb indices, in: I. Gutman, B. Furtula (eds.), Recent Results in the Theory of Randić index, University of Kragujevac, Kragujevac, 2008, pp. 205-209.; B. Liu, On a conjecture about comparing Zagreb indices, in: I. Gutman, B. Furtula (eds.), Recent Results in the Theory of Randić index, University of Kragujevac, Kragujevac, 2008, pp. 205-209. |
| [15] | Ilić, A.; Stevanović, D., On comparing Zagreb indices, MATCH Commun. Math. Comput. Chem., 62, 681-687 (2009) · Zbl 1274.05095 |
| [16] | Sun, L.; Wei, S., Comparing the Zagreb indices for connected bicyclic graphs, MATCH Commun. Math. Comput. Chem., 62, 699-714 (2009) · Zbl 1274.05110 |
| [17] | Liu, B.; You, Z., A Survey on Comparing Zagreb Indices, MATCH Commun. Math. Comput. Chem., 65, 581-593 (2011) · Zbl 1265.05123 |
| [18] | D. Cvetković, Graphs and their spectra Grafovi i njihovi spektri (Thesis), Univ. Beograd Publ. Elektrotehn. Fak., Ser. Mat. Fiz., 1971, 1-50 (354-356).; D. Cvetković, Graphs and their spectra Grafovi i njihovi spektri (Thesis), Univ. Beograd Publ. Elektrotehn. Fak., Ser. Mat. Fiz., 1971, 1-50 (354-356). |
| [19] | Cvetković, D.; Doob, M.; Sachs, H., Spectra of Graphs—Theory and Application. Spectra of Graphs—Theory and Application, Johann Ambrosius Barth Verlag (1995), Heidelberg: Heidelberg Leipzig · Zbl 0824.05046 |
| [20] | Khalifeh, M. H.; Yousefi-Azari, H.; Ashrafi, A. R., The first and second Zagreb indices of some graph operations, Discrete Appl. Math., 157, 804-811 (2009) · Zbl 1172.05314 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
