On the upper bounds for the degree deviation of graphs. (English) Zbl 1479.05058
Summary: Let \(G\) be a simple connected non-trivial graph of order \(n\), size \(m\), and vertex degree sequence \((d_1, d_2,\ldots , d_n)\). The first Zagreb index \(M_1\), forgotten index \(F\) and inverse degree ID are the graph invariants defined as \(M_1(G)=\sum_{i=1}^n d_i^2, F(G) = \sum_{i=1}^n d_i^3\) and \(ID(G)=\sum_{i=1}^n \frac{1}{d_i} \), respectively. A graph is said to be regular if all of its vertices have the same degree and otherwise, it is called a nonregular graph. For the quantitative topological characterization of the nonregularity of graphs, the graph invariants \(s(G)=\sum_{i=1}^n\left| d_i-\frac{2m}{n}\right|\) and \(\operatorname{Var}(G)= \frac{1}{n}\sum_{i=1}^n \left( d_i - \frac{2m}{n} \right)^2\) may be used. In this paper, some upper bounds for \(s(G)\) that reveal connections between \(s(G)\) and \(M_1(G)\), \(F(G)\), \(ID (G)\), \(\operatorname{Var}(G)\) are obtained.
MSC:
| 05C09 | Graphical indices (Wiener index, Zagreb index, Randić index, etc.) |
| 05C07 | Vertex degrees |
| 05C92 | Chemical graph theory |
| 92E10 | Molecular structure (graph-theoretic methods, methods of differential topology, etc.) |
Keywords:
irregularity of graph; degree deviation; first Zagreb index; forgotten topological index; inverse degreeSoftware:
GRAFFITIReferences:
| [1] | Abdo, H.; Brandt, S.; Dimitrov, D., The total irregularity of a graph, Discret Math. Theor. Comput. Sci., 16, 201-206 (2014) · Zbl 1288.05130 |
| [2] | Albertson, Mo, The irregularity of graph, Ars Comb., 46, 219-225 (1997) · Zbl 0933.05073 |
| [3] | Ali, A.; Gutman, I.; Milovanović, E.; Milovanović, I., Sum of powers of the degrees of graphs: extremal results and bounds, MATCH Commun. Math. Comput. Chem., 80, 5-84 (2018) · Zbl 1468.05288 |
| [4] | Bell, Fk, A note on the irregularity of graphs, Linear Algebra Appl., 161, 45-54 (1992) · Zbl 0776.05069 · doi:10.1016/0024-3795(92)90004-T |
| [5] | Borovićanin, B.; Das, Kc; Furtula, B.; Gutman, I., Bounds for Zagreb indices, MATCH Commun. Math. Comput. Chem., 78, 17-100 (2017) · Zbl 1471.92406 |
| [6] | Borovićanin, B., Das, K.C., Furtula, B., Gutman, I.: Zagreb indices: bounds and extremal graphs. In: I. Gutman, B. Furtula, K.C. Das, E. Milovanović, I. Milovanović (eds) Bounds in Chemical Graph Theory-Basics, Mathematical Chemistry Monographs, MCM 19, Univ. Kragujevac, Kragujevac, pp. 67-153. (2017) |
| [7] | Collatz, L.; Sinogowitz, U., Spektren endlicher Graphen, Abh. Math. Sem. Univ. Hamburg, 21, 63-77 (1957) · Zbl 0077.36704 · doi:10.1007/BF02941924 |
| [8] | Criado, R.; Flores, J.; Del Amo, Ag; Romance, M., Centralities of a network and its line graph: an analytical comparison by means of their irregularity, Int. J. Comput. Math., 91, 304-314 (2014) · Zbl 1291.05198 · doi:10.1080/00207160.2013.793316 |
| [9] | Dimitrov, D.; Réti, T., Graphs with equal irregularity indices, Acta Polytechn. Hung., 11, 41-57 (2014) |
| [10] | Edwards, Cs, The largest vertex degree sum for a triangle in a graph, Bull. London Math. Soc., 9, 203-208 (1977) · Zbl 0357.05058 · doi:10.1112/blms/9.2.203 |
| [11] | Elphick, C.; Wocjan, P., New measures of graph irregularity, El. J. Graph Theory Appl., 2, 1, 52-65 (2014) · Zbl 1306.05105 · doi:10.5614/ejgta.2014.2.1.5 |
| [12] | Fajtlowicz, S., On conjectures on Graffiti-II, Congr. Numer., 60, 187-197 (1987) |
| [13] | Fath-Tabar, Gh, Old and new Zagreb indices of graphs, MATCH Commun. Math. Comput. Chem., 65, 79-84 (2011) · Zbl 1265.05146 |
| [14] | Furtula, B.; Gutman, I., A forgotten topological index, J. Math. Chem., 53, 1184-1190 (2015) · Zbl 1317.05031 · doi:10.1007/s10910-015-0480-z |
| [15] | Goldberg, F.: New results on eigenvalues and degree deviation, arXiv:1403.2629 [math.CO] (2014) |
| [16] | Gutman, I.; Furtula, B.; Elphick, C., Three new/old vertex-degree-based topological indices, MATCH Commun. Math. Comput. Chem., 72, 617-632 (2014) · Zbl 1464.05076 |
| [17] | Gutman, I., Irregularity of molecular graphs, Kragujevac J. Sci., 38, 71-81 (2016) · doi:10.5937/KgJSci1638071G |
| [18] | Gutman, I.; Trinajstić, N., Graph theory and molecular orbitals. Total \(\pi \)-electron of alternant hydrocarbons, Chem. Phys. Lett., 17, 535-538 (1972) · doi:10.1016/0009-2614(72)85099-1 |
| [19] | Gutman, I.; Das, Kc; Furtula, B.; Milovanović, E.; Milovanović, I., Generalizations of Szőkefalvi Nagy and Chebyshev inequalities with applications in spectral graph theory, Appl. Math. Comput., 313, 235-244 (2017) · Zbl 1353.62113 · doi:10.1016/j.cam.2016.09.025 |
| [20] | Hamzah, A.; Réti, T., An analogue of Zagreb index inequality obtained from graph iregularity measures, MATCH Commun. Math. Comput. Chem., 72, 669-683 (2014) · Zbl 1464.05079 |
| [21] | Haviland, J., On irregularity in graphs, Ars Combin., 78, 283-288 (2006) · Zbl 1164.05335 |
| [22] | Hosamani, Sm; Basavanagoud, B., New upper bounds for the first Zagreb index, MATCH Commun. Math. Comput. Chem., 74, 97-101 (2015) · Zbl 1462.05085 |
| [23] | Izumino, S.; Mori, H.; Seo, Y., On Ozeki’s inequality, J. Ineq. Appl., 2, 235-253 (1998) · Zbl 0937.47021 |
| [24] | Lawrence, C.J., Tizzard, K., Haviland, J.: Disease-spread and stochastic graphs. In: Proceedings of International Conference on Social Networks, London, pp. 143-150. (1995) |
| [25] | Liu, L.; Kang, L.; Shan, E., On the irregularity of uniform hypergraphs, Eur. J. Combin., 71, 22-32 (2018) · Zbl 1387.05172 · doi:10.1016/j.ejc.2018.02.034 |
| [26] | Mansour, T.; Rostami, Ma; Suresh, E.; Xavier, Gba, New sharp lower bounds for the first Zagreb index, Sci. Publ. State Univ. Novi Pazar Ser. A Appl. Math. Inform. Mech., 8, 1, 11-19 (2016) · doi:10.5937/SPSUNP1601011M |
| [27] | Milovanović, Iž; Ćirić, Vm; Milentijević, Iz; Milovanović, Ei, On some spectral vertex and edge degree-based graph invariants, MATCH Commun. Math. Comput. Chem., 77, 177-188 (2017) · Zbl 1466.92275 |
| [28] | Milovanović, Ei; Milovanović, Iž, Sharp bounds for the first Zagreb index and first Zagreb coindex, Miskolc Math. Notes, 16, 1017-1024 (2015) · Zbl 1349.05183 · doi:10.18514/MMN.2015.1274 |
| [29] | Milovanović, Iž; Milovanović, Ei, Correcting a paper on first Zagreb index, MATCH Commun. Math. Comput. Chem., 74, 693-695 (2015) · Zbl 1476.05036 |
| [30] | Milovanović, Iž; Milovanović, Ei; Ćirić, V.; Jovanović, N., On some irregularity measures of graphs, Sci. Publ. State Univ. Novi Pazar Ser. A Appl. Math. Inform. Mech., 8, 1, 21-34 (2016) · doi:10.5937/SPSUNP1601021M |
| [31] | Mitrinović, Ds; Pečarić, Je; Fink, Am, Classical and New Inequalities in Analysis (1993), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 0771.26009 |
| [32] | Nikiforov, V., Eigenvalues and degree deviation in graphs, Linear Algebra Appl., 414, 347-360 (2006) · Zbl 1092.05046 · doi:10.1016/j.laa.2005.10.011 |
| [33] | De Oliveira, Ja; Oliveira, Cs; Justel, C.; De Abreu, Nmm, Measures of irregularity of graphs, Pesq. Oper., 33, 383-398 (2013) · doi:10.1590/S0101-74382013005000012 |
| [34] | Radon, J., Theorie und Anwendungen der absolut odditiven Mengenfunktionen, Sitzungsber. Acad. Wissen. Wien, 122, 1295-1438 (1913) · JFM 44.0464.03 |
| [35] | Rodriguez, Jm; Sanchez, Jl; Sigarreta, Jm, CMMSE-on the first general Zagreb index, J. Math. Chem., 56, 7, 1849-1864 (2018) · Zbl 1401.92225 · doi:10.1007/s10910-017-0816-y |
| [36] | Réti, T.; Toth-Loufer, F., On the construction and comparison of graph irregularity indices, Kragujevac J. Sci, 39, 68-88 (2017) |
| [37] | Réti, T., Graph irregularity and a problem raised by Hong, Acta Polytechn. Hung., 15, 6, 27-43 (2018) |
| [38] | Zhou, B., New upper bounds for Laplacian energy, MATCH Commun. Math. Comput. Chem., 62, 553-560 (2009) · Zbl 1224.05332 |
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.
