On some irregularity measures of graphs
Authors: Milovanović Ž., Milovanović E.I., Irić V.Ć., Jovanović N.
Keywords: Zagreb indices; irregularity measures; inequalities
Abstract:
Let Γ(G) be a set of all simple graphs of order n and size m, without isolated vertices, with vertex degree sequence d1 ≥ d2 ≥ … ≥ dn > 0. A graph G is regular if and only if d1 = d2 = … = dn . Each mapping Irr: Γ(G) ›→ [0, +∞) with the property Irr(G) = 0 if and only if G is regular, is referred to as irregularity measure of graph. In this paper we introduce some new irregularity measures and inequalities that establish relations between them.
References:
[1] Abdo, H., Brandt, S., Dimitrov, D. (2014) The total irregularity of a graph. Discr. Math. Theor. Comput. Sci., 201-206; 16
[2] Albertson, M.O. (1997) The irregularity of a graph. Ars Combinatoria, 46, 219-225
[3] Andrica, D., Badea, C. (1988) Gr\’uss’ inequality for positive linear functionals. Periodica Mathematica Hungarica, 19, 2, 155-167
[4] Bell, F.K. (1992) A note on the irregularity of graphs. Linear Algebra and its Applications, 161, 45-54
[5] Biggs, N.L. (1993) Algebraic graph theory. Cambridge, itd: Cambridge University Press / CUP
[6] Caporossi, G., Hansen, P. (2000) Variable neighborhood search for extremal graphs: 1 The AutoGraphiX system. Discrete Mathematics, 212(1-2): 29-44
[7] Cerone, P., Dragomir, S.S. (2007) A refinement of the Gruss inequality and applications. Tamkang J. Math, 38, 1, 34-49
[8] Chung, F.R.K. (1997) Spectral graph theory. Providence, RI: American Mathematical Society / AMS
[9] Collatz, L., Sinogowitz, U. (1957) Spektren endlicher Grafen. Abh. Math. Sem. Univ. Hamburg, 21, 63-77
[10] Das, K.Ch., Xu, K., Nam, J. (2015) Zagreb indices of graphs. Frontiers of Mathematics in China, 10(3): 567-582
[11] de Caen, D. (1998) An upper bound on the sum of squares of degrees in a graph. Discrete Mathematics, 185(1-3): 245-248
[12] de N. (2012) Some bounds of reformulated Zagreb indices. Appl. Math. Sci, 6 (101), 5005- 5012
[13] Edwards, C.S. (1977) The Largest Vertex Degree Sum for a Triangle in a Graph. Bulletin of the London Mathematical Society, 9(2): 203-208
[14] Elphick, C., Department of Electrical Engineering and Computer Science University of Central Florida, Wocjan, P. (2014) English. Electronic Journal of Graph Theory and Applications, 2(1): 52-65
[15] Fath-Tabar, G.H. (2011) Old and new Zagreb indices of graphs. Communications in Mathematical and in Computer Chemistry / MATCH, vol. 65, br. 1, str. 79-84
[16] Furtula, B., Gutman, I. (2015) A forgotten topological index. Journal of Mathematical Chemistry, 53(4): 1184-1190
[17] Furtula, B., Gutman, I., Ediz, S. (2014) On difference of Zagreb indices. Discrete Applied Mathematics, 178: 83-88
[18] Goldberg, F. (2014) Spectral radius minus average degree: A better bound. arXiv: 1407.4285v1 [math.co] 16 July
[19] Gutman, I., Furtula, B., Elphick, C. (2014) The new/old vertex-degree-based topological indices. MATCH Commun. Math. Comput. Chem., 617-632; 72
[20] Gutman, I., Furtula, B., Kovijanić, Ž. (2015) On Zagreb indices and coindices. MATCH Commun. Math. Comput. Chem., 5-16; 74
[21] Gutman, I., Trinajstić, N. (1972) Graph theory and molecular orbitals. Total φ-electron energy of alternant hydrocarbons. Chemical Physics Letters, 17(4): 535-538
[22] Gutman, I. (2013) Degree-Based Topological Indices. Croatica Chemica Acta, 86(4): 351-361
[23] H., Abdo, H., DimiItrov, D., Reti, T., Stevanović, D. (2014) Estimating the spectral radius of a graph by the second Zagreb index. MATCH Commun. Math. Comput. Chem., 741-751; 72
[24] Hamzeh, A., Reti, T. (2014) An analogue of Zagreb index inequality obtained from graph irregularity measures. MATCH Commun. Math. Comput. Chem, 72, 669-683
[25] Ilic, A., Stevanovic, D.P. (2009) On Comparing Zagreb Indices. MATCH commun. math. comput. chem., =vol. 62, br. 3, str. 681-687
[26] Ilić, A., Zhou, B. (2012) On reformulated Zagreb indices. Discr. Appl. Math, 160, 204-209
[27] Mili, A., Ević, Ć., Nikolić, S. (2004) On variable Zagreb idices. Croat. Chem. Acta, 97-101; 77
[28] Milicević, A., Nikolić, S., Trinajstić, N. (2004) On reformulated Zagreb indices. Molecular diversity, 8(4): 393-9
[29] Milovanović, E., Glogić, E., Milovanović, I., Cvjetković, M. (2015) Irregularity measures of graph. Scientific Publications of the State University of Novi Pazar Series A: Applied Mathematics, Informatics and mechanics, vol. 7, br. 2, str. 105-115
[30] Milovanović, I.Ž., Milovanović, E.I. (2000) Discrete mathematics. Univ. Niš, In serbian
[31] Mitrinović, D.S., Pečarić, J.E., Fink, A.M. (1993) Classical and new inequalities in analysis. Dordrecht, itd: Kluwer Academic Publishers
[32] Mitrinović, D.S., Vasić, P.M. (1970) Analytic inequalities. Berlin, itd: Springer-Verlag
[33] Nagy, J.V.S. (1918) Uber algebraische Gleichungen mit lauter reellen Wurzeln. Jahresbericht der deutschen mathematiker-Vereingung, 27, 37-43
[34] Nikiforov, V. (2006) Walks and the spectral radius of graphs. Linear Algebra Appl, 418, 257-268
[35] Nikolić, S., Kovačević, G., Miličević, A., Trinajstić, N. (2003) The Zagreb indices 30 years after. Croat. Chem. Acta, 76 (2), 113-124
[36] Popoviciu, T. (1935) Sur les equations algebriques ayant toutes leurs raeines reelles. Mathematica, 9, 129-145
[37] Rada, J., Cruz, R. (2014) Vertex-degree-based topological indices over graphs. MATCH Commun. Math. Comput. Chem., 72, 603-616
[38] Réti, T., Felde, I. Novel Zagreb indices-based inequalities with particular regard to semiregular and generalized semiregular graphs. ArXiv.org/pdf/1509.08015
[39] Sharma, R., Gupta, M., Kapoor, G. (2010) Some better bounds on the variance with applications. Journal of Mathematical Inequalities, (3): 355-363
[40] Todeschini, R., Consonni, V. (2000) Handbook of molecular descriptors for chemoinformatics. Weinheim: Wiley-VCH
[41] Todeschini, R., Consonni, V. (2009) Molecular Descriptors for Chemoinformatics. Weinheim: Wiley-VCH
[42] Trinajstić, N. (1992) Chemical graph theory. Boca Raton: CRC Press, revised edn
[43] Vukičević, D., Gutman, I., Furtula, B., Andova, V., Dimitrov, D. (2011) Some observations on comparing Zagreb indices. Communications in Mathematical and in Computer Chemistry / MATCH, vol. 66, br. 2, str. 627-645
[44] Yoon, Y.S., Kim, J.K. (2006) A relationship between bounds on the sum of squares of degrees of a graph. Journal of Applied Mathematics and Computing, 21(1-2): 233-238
[45] Zhou, B., Trinajstić, N. (2010) Some properties of the reformulated Zagreb indices. Journal of Mathematical Chemistry, 48(3): 714-719