Irregularity measures of graph

Authors: E. Milovanović, E. Glogić, I. Milovanović, M. Cvjetković

Keywords: irregularity measures (of graph); Zagreb index; Randić index

Abstract:

Let G = (V,E), V = {1,2 …, n}, be a simple graph without isolated vertices, with vertex degree sequence d1 ≥ d2 ≥ … ≥ dn > 0, di = d(i). A graph G is regular if and only if d1 = d2 = … = dn. A graph invariant I(G) is measure of irregularity of graph G with the property I(G)=0 if and only if G is regular, and I(G)>0 otherwise. In this paper we introduce some new irregularity measures.

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] Bell, F.K. (1992) A note on the irregularity of graphs. Linear Algebra and its Applications, 161, 45-54 [4] Biggs, N.L. (1993) Algebraic graph theory. Cambridge, itd: Cambridge University Press / CUP [5] Cavers, M. (2010) The normalized Laplacian matrix and general Randi’c index of graphs. Saskichewan: University of Regina, A Thesis [6] Cavers, M., Fallat, S., Kirkland, S. (2010) On the normalized Laplacian energy and general Randić index of graphs. Linear Algebra and its Applications, 433(1): 172-190 [7] Chung, F.R.K. (1997) Spectral graph theory. Providence, RI: American Mathematical Society / AMS [8] Collatz, L., Sinogowitz, U. (1957) Spektren endlicher Grafen. Abh. Math. Sem. Univ. Hamburg, 21, 63-77 [9] Das, K.Ch., Xu, K., Nam, J. (2015) Zagreb indices of graphs. Frontiers of Mathematics in China, 10(3): 567-582 [10] De N. (2012) Some bounds of reformulated Zagreb indices. Appl. Math. Sci., 6(101), 5005-5012 [11] 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 [12] Elphick, C., Wocjan, P. (2014) New measures of graph irregularity. El. J. Graph. Theory Appl., 2 (1); 52-65 [13] Fath-Tabar, G.H. (2011) Old and new Zagreb indices of graphs. Communications in Mathematical and in Computer Chemistry, vol. 65, br. 1, str. 79-84 [14] Favaron, O., Mahéo, M., Saclé, J.-F. (1993) Some eigenvalue properties in graphs (conjectures of Graffiti — II). Discrete Mathematics, 111(1-3): 197-220 [15] Goldberg, F. (2014) Spectral radius minus average degree: A better bound. arXiv: 1407.4285v1, [math.co], 16 July [16] Gutman, I., Robbiano, E., Mortins, A., Cordoso, D.M., Medino, L., Rojo, O. (2010) Energy of line graphs. Linaear Algebra Appl., 433, 1312-1323 [17] Gutman, I., Furtula, B., ur. (2008) Recent Results in the Theory of Randić Index. Kragujevac [18] Gutman, I., Trinajstić, N. (1972) Graph theory and molecular orbitals. Total φ-electron energy of alternant hydrocarbons. Chemical Physics Letters, 17(4): 535-538 [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. (2010) Novel molecular descriptors-theory and applications I. Kragujevac: University, Faculty of Science [21] Hamzeh, A., Reti, T. (2014) An analogue of Zagreb index inequality obtained from graph irregularity measures. MATCH Commun. Math. Comput. Chem., 669-683; 72 [22] Hao, J. (2011) Theorems about Zagreb indices and modified Zagreb indices. Communications in Mathematical and in Computer Chemistry / MATCH, vol. 65, br. 3, str. 659-670 [23] Ilic, A., Stevanovic, D.P. (2009) On Comparing Zagreb Indices. MATCH commun. math. comput. chem., =vol. 62, br. 3, str. 681-687 [24] Ilić, A., Zhou, B. (2012) On reformulated Zagreb indices. Discrete Applied Mathematics, 160(3): 204-209 [25] Li, X., Gutman, I. (2006) Mathematical aspects of Randić-type molecular structure descriptors. Kragujevac: University, Faculty of Science [26] Liu, B., Gutman, I. (2007) Estimating the Zagreb and the general randic indices. Communications in Mathematical and in Computer Chemistry, vol. 57, br. 3, str. 617-632 [27] Liu, M., Liu, B. (2012) On sum of powers of the singless Laplacian eigenvalues of graphs. Hacettepe J. Math. Statis, 41(4), 527-536 [28] Milićević, A., Nikolić, S. (2004) On variable Zagreb idices. Croat. Chem. Acta, 97-101; 77 [29] Milićević, A., Nikolić, S., Trinajstić, N. (2004) On reformulated Zagreb indices. Mol. Divers, 393-399; 8 [30] Mitrinović, D.S., Pečarić, J.E., Fink, A.M. (1993) Classical and new inequalities in analysis. Dordrecht: Kluwer Academic Publisher [31] Mitrinović, D.S. (1970) Analytic inequalities. Berlin, itd: Springer Verlag [32] Nikiforov, V. (2006) Eigenvalues and degree deviation in graphs. Linear Algebra and its Applications, 414(1): 347-360 [33] Nikolić, S., Kovačević, G., Miličević, A., Trinajstić, N. (2003) The Zagreb indices 30 years after. Croat. Chem. Acta, 76 (2), 113-124 [34] Randić, M. (1975) On characterization of molecular branching. J. Am. Chem. Soc., 97, 6609-6615 [35] Shi, L. (2009) Bounds on Randić indices. Discrete Mathematics, 309(16): 5238-5241 [36] Tian, G., Huang, T., Cui, S. (2012) Bounds on the algebraic connectivity of graphs. Advances Math., 41(2), 217-224 [37] Todeschini, R., Consonni, V. (2000) Molecular Descriptors for Chemoinformatics. Weinheim: Wiley-VCH [38] Todeschini, R., Consonni, V. (2009) Molecular Descriptors for Chemoinformatics. Weinheim: Wiley-VCH [39] Trinajstić, N. (1992) Chemical graph theory. Boca Raton: CRC Press, revised edn [40] 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 [41] Vukičević, D., Trinajstić, N. (2003) Modified Zagreb M2 index: Comparison with the Randić connectivity index for benzenoid systems. Croat Chem Acta, 76(2), 183-187 [42] 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 [43] Zhou, B., Luo, W. (2009) A note on general Randić index. MATCH Commun. Math. Comput. Chem., 62, 155-162 [44] Zumstein, P. (2005) Comparison of spectral methods through the adjacency matrix and the Laplacian of a graph. Zürich: ETH, Th. Diploma