Remark on the Irregularity of Graphs
Authors: S. Stankov, E. Dolicanin, M. Matejic, E. Milovanovic, I. Milovanovic
Keywords: Topological indices, irregularity (of a graph)
Abstract:
Let G = (V,E), V = {v1,v2, . . . ,vn}, E = {e1,e2, . . . ,em}, be a simple connected graph with the vertex degree sequence Δ = d1 ≥ d2 ≥ · · · ≥ dn =δ > 0, di = d(vi). The zeroth–order general Randi´c index, 0Rα (G), of a connected graph G, is defined as 0Rα (G) = Σni=1 dα i .A linear combination of 0Rα (G) of the form irr(α)(G) = 0Rα+1(G)− 2m n 0Rα (G), α ≥ 0, can be considered as an irregularity measure of a graph since irr(α)(G) = 0 if and only if G is a regular graph, and irr(α)(G) > 0 otherwise. In this paper we consider a linear combination irr(α)(G)− 2m n irr(α−1)(G), for α ≥ 1, which can be also considered as irregularity measure of graph, and determine its bounds.
References:
[1] A. T. BALABAN I. MOTOC, D. BONCHEV, D. MEKENYAN, Topological indices for structure–activity correlations, Topics Curr. Chem. 111 ( 1983) 21–55.
[2] I. GUTMAN, N. TRINAJSTIC, Graph theory and molecular orbitals. Total π-electron energy of alternant hydrocarbons, Chem. Phys. Lett. 17 (1972) 535–538.
[3] A. ALI, I. GUTMAN, E. MILOVANOVIC, I. MILOVANOVIC, Sum of powers of the degrees of graphs: extremal results and bounds, MATCH Commun. Math. Comput. Chem. 80 (2018) 5–84.
[4] B. BOROVICANIN, K. C. DAS, B. FURTULA, I. GUTMAN, Bounds for Zagreb indices, MATCH Commun. Math. Comput. Chem. 78 (2017) 17–100.
[5] B. BOROVICANIN, K. C. DAS, B. FURTULA, I. GUTMAN, Zagreb indices: Bounds and extremal graphs, In: Bounds in Chemical Graph Theory – Basics, I. Gutman, B. Furtula, K. C. Das, E. Milovanovi´c, I. Milovanovi´c, Eds., Univ. Kargujevac, Kragujevac, 2017, pp. 67– 153.
[6] I. GUTMAN, K. C. DAS, The first Zagreb index 30 years after, MATCH Commun. Math. Comput. Chem. 50 (2004) 83–92.
[7] S. NIKOLIC , G. KOVACEVIC, A. MILICEVIC, N. TRINAJSTIC , The Zagreb indices 30 years after, Croat. Chem. Acta 70 (2003) 113–124.
[8] Y. HO, X. LI, Y. SHI, T. XU, I. GUTMAN, On molecular graphs with smallest and greatest zeroth–order general Randi´c index, MATCH Commun. Math. Comput. Chem. 54 (2005) 425–434.
[9] X. LI, J. ZHANG, A unified approach to the extremal trees for different indices, MATCH Commun. Math. Comput. Chem. 54 (2005) 195–208.
[10] A. MILICEVIC, S. NIKOLIC, On variable Zagreb indices, Croat. Chem. Acta 77 (2004) 97–101.
[11] S. FAJTLOWICZ, On conjectures on Graffiti-II, Congr. Numer. 60 (1987) 187–197.
[12] B. FURTULA, I. GUTMAN, A forgotten topological index, J. Math. Chem. 53 (2015) 1184–1190.
[13] I. GUTMAN, Topological indices and irregularity measures, Bull. Inter. Math. Virt. Inst. 8(2018) 469–475.
[14] F. K. BELL, A note on the irregularity of graphs, Linear Algebra Appl. 16 (1992) 45–54.
[15] A. HAMZEH, T. RETI, An analogue of Zagreb index inequality obtained from graph irregularity measures, MATCH Commun. Math. Comput. Chem. 72 (2014) 669–683.
[16] V. NIKIFOROV, Eigenvalues and degree deviation in graphs, Linear Algebra Appl. 414 (2006) 347–360.
[17] I.ˇZ . MILOVANOVIC, E. I. MILOVANOVIC, V. CIRIC, N. JOVANOVIC, On some irregularity measures of graphs, Sci. Publ. State Univ. Novi Pazar Ser. A: Appl. Math. Inform. Mech. 8(1) (2016) 21–34.
[18] A. ALI, E. MILOVANOVIC, M. MATEJIC, I. MILOVANOVIC , On the upper bounds for the degree–deviation of graphs, J. Appl. Math. Comput. 62 (2020) 179–187.
[19] I. GUTMAN, B. FURTULA, C. ELPHICK, Three new/old vertex–degree–based topological indices, MATCH Commun. Math. Comput. Chem. 72 (2014) 617–632.
[20] T. RETI, A. ALI, On the variance–type graph irregularity measures, Commun. Comb. Optim. 5(2) (2020) 169–178.
[21] T. RETI, I. MILOVANOVIC , E. MILOVANOVIC, M. MATEJIC , On graph irregularity indices with particular regard to degree deviation, Filomat 35 (11) (2021) 3689–3701.
[22] S. M. CIOABA, Sums of powers of the degree of a graph, Discr. Math. 306 (2006) 1959–1964.
[23] C. S. EDWARDS, The largest vertex degree sum for a triangle in a graph, Bull. London Math. Soc. 9 (1977) 203–208.
[24] E. I. MILOVANOVIC , I. Z. MILOVANOVIC, Sharp bounds for the first Zagreb index and first Zagreb coindex, Miskolc Math. Notes 16(2) (2015) 1017–1024.
[25] I. GUTMAN, K. CH. DAS, B. FURTULA, E. MILOVANOVIC, I. MILOVANOVIC, Generalizations of Szokefalvi Nagy and Chebyshev inequalities with applications in spectral graph theory, Appl. Math. Comput. 313 (2017) 235–244.
[26] A. ILIC , D. STEVANOVIC, On comparing Zagreb indices, MATCH Commun. Math. Comput. Chem. 62 (2009) 681–687.
[27] J. L. W. V. JENSEN, Sur les fonctions convexes of les integralites entre les values moyennes, Acta Math. 30 (1906) 175–193.
[28] D. S. MITRINOVIC, P. M. VASIC, The centroid method in inequalities, Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. Fiz. 498–541 (1975) 3–16.
[29] D. S. MITRINOVIC , J. E. PECARIC , A. M. FINK, Inequalities involving functions and their integrals and derivatives, Kluwer Academic Publishers, Dordrecht–Boston–London, 1991.
[30] S. D. STANKOV, M. M. MATEJIC , I. Z . MILOVANOVIC , E. I. MILOVANOVIC, S¸ . B. BOZKURT ALTINDAG, Some new bounds on the Zagreb index, Electron. J. Math. 1 (2021) 101–107.
[31] B. FURTULA, I. GUTMAN, Z . KOVIJANIC VUKICEVIC, G. LEKISHVILI, G. POPIVODA, On an old/new degree–based topological index, Bull. Acad. Serbe Sci. Arts (Cl. Sci Math. Natur) 40 (2015) 19–31.
[32] S. ZHANG, H. ZHANG, Unicyclic graphs with the first three smallest and largest general Zagreb index, MATCH Commun. Math. Comput. Chem. 55 (2006) 427–438.