On the Variance-Type Graph Irregularity Measures

Document Type : Short notes

Authors

1 Obuda University, Budapest, Hungary

2 University of Hail, Hail, Saudi Arabia

Abstract

Bell's degree-variance Var$\!{}_{B}$ for a graph $G$, with the degree sequence ($d_1,d_2,\ldots,d_n$) and size $m$, is defined as $Var\!_{B} (G)=\frac{1}{n} \sum _{i=1}^{n}\left[d_{i} -\frac{2m}{n}\right]^{2}$. In this paper, a new version of the irregularity measures of variance-type, denoted by $Var_q$, is introduced and discussed. Based on a comparative study, it is demonstrated that the newly proposed irregularity measure $Var_q$ possess a better discrimination ability than the classical Bell's degree-variance in several cases.

Keywords

Main Subjects

References

[1] M.O. Albertson, The irregularity of a graph, Ars Combin. 46 (1997), 219–225.
[2] A. Ali and T. Réti, Two irregularity measures possessing high discriminatory ability, arXiv preprint arXiv:1904.05053 (2019).
[3] M. Behzad and G. Chartrand, No graph is perfect, Amer. Math. Monthly 74 (1967), no. 8, 962–963.
[4] F.K. Bell, A note on the irregularity of graphs, Linear Algebra Appl. 161 (1992), 45–54.
[5] N. Biggs, Algebraic Graph Theory, Cambridge Univ. Press, Cambridge, 1974.
[6] P.O. Boaventura-Netto, Graph irregularity: discussion, graph extensions and new proposals, Revista de Matem´atica: Teoría y Aplicaciones 22 (2015), no. 2, 293–310.
[7] P.O. Boaventura-Netto, G. Caporossi, and L.S. de Lima, Exhaustive and metaheuristic exploration of two new structural irregularity measures, vol. 82, GERAD HEC Montréal, 2019.
[8] B. Borovićanin, S. Grünewald, I. Gutman, and M. Petrović, Harmonic graphs with small number of cycles, Discrete Math. 265 (2003), no. 1-3, 31–44.
[9] Y. Caro and R. Yuster, Graphs with large variance, Ars Combin. 57 (2000), no. 1-3, 151–162.
[10] J.S. Coleman, Introduction to Mathematical Sociology, Free Press, New York, 1964.
[11] L. Collatz and U. Sinogowitz, Spektren endlicher grafen, Abh. Math. Sem. Univ. Hamburg, vol. 21, Springer, 1957, pp. 63–77.
[12] J.A. de Oliveira, C.S. Oliveira, C. Justel, and N.M.M. de Abreu, Measures of irregularity of graphs, Pesquisa Operacional 33 (2013), no. 3, 383–398.
[13] D. Dimitrov, S. Brandt, and H. Abdo, The total irregularity of a graph, Discrete Math. Theor. Comput. Sci. 16 (2014), no. 6, 201–206.
[14] C. Elphick and T. Réti, On the relations between the Zagreb indices, clique numbers and walks in graphs, MATCH Commun. Math. Comput. Chem. 74 (2015), no. 1, 19–34.
[15] E. Estrada, Randić index, irregularity and complex biomolecular networks, Acta Chim. Slov. 57 (2010), no. 3, 597–603.
[16] S. Fajtlowicz, On conjectures of Graffiti. II, Congr. Numer. 60 (1987), 187–197.
[17] B. Furtula and I. Gutman, A forgotten topological index, J. Math. Chem. 53 (2015), no. 4, 1184–1190.
[18] A. Ghalavand and T. Sohail, On some variations of the irregularity, Discrete Math. Lett. 3 (2020), 25–30.
[19] C. Godsil and v Royle, Algebraic Graph Theory, Springer-Verlag, New York, 2001. 
[20] I. Gutman, Topological indices and irregularity measures, Bulletin of the International Mathematical Institute 8 (2018), 469–475.
[21] I. Gutman and K.C. Das, The first Zagreb index 30 years after, MATCH Commun. Math. Comput. Chem. 50 (2004), no. 1, 83–92.
[22] I. Gutman, P. Hansen, and H. Mélot, Variable neighborhood search for extremal graphs. 10. comparison of irregularity indices for chemical trees, J. Chem. Inf. Model. 45 (2005), no. 2, 222–230.
[23] I. Gutman and P. Paule, The variance of the vertex degrees of randomly generated graphs, Univ. Beograd, Publ. Elektrotehn. Fak. Ser. Mat. 13 (2002), 30–35.
[24] I. Gutman, M. Togan, A. Yurttas, A.S. Cevik, and I.N. Cangul, Inverse problem for sigma index, MATCH Commun. Math. Comput. Chem 79 (2018), no. 2, 491–508.
[25] A. Ili´c and D. Stevanović, On comparing Zagreb indices, MATCH Commun. Math. Comput. Chem. 62 (2009), no. 3, 681–687.
[26] R. Merris, Antiregular graphs are universal for trees, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 14 (2003), 1–3.
[27] V. Nikiforov, Eigenvalues and degree deviation in graphs, Linear Algebra Appl. 414 (2006), no. 1, 347–360.
[28] S. Nikolić, G. Kovačević, A. Miličević, and N. Trinajstić, The Zagreb indices 30 years after, Croat. Chem. Acta 76 (2003), no. 2, 113–124.
[29] T. R´eti, On some properties of graph irregularity indices with a particular regard to the σ-index, Appl. Math. Comput. 344 (2019), 107–115.
[30] T. Réti and A. Ali, Some generalizations of the total irregularity of graphs, Scientific Publications of the State University of Novi Pazar, Ser. A: Appl. Math. Inform. Mech. 11 (2019), no. 1, 1–9.
[31] T. Réti and A. Ali, On the comparative study of nonregular networks, IEEE 23rd International Conference on Intelligent Engineering Systems, G¨od¨oll˝o, Hungary (April 25-27, 2019), 289–293.
[32] T. Réti and A. Drégelyi-Kiss, On the generalization of harmonic graphs, Discrete Math. Lett. 1 (2019), 16–20.
[33] T. Réti, R. Sharafdini, A. Drégelyi-Kiss, and H. Haghbin, Graph irregularity indices used as molecular descriptors in QSPR studies, MATCH Commun. Math. Comput. Chem. 79 (2018), no. 2, 509–524.
[34] T. Réti and E. T´oth-Laufer, On the construction and comparison of graph irregularity indices, Kragujevac J. Sci. 39 (2017), 53–75.
[35] K. Smith and J. Escudero, Normalized degree variance: a network heterogeneity index unbiased to size and density, arXiv:1803.03057.
[36] K. Smith and J. Escudero, The complex hierarchical topology of EEG functional connectivity, J. Neurosci. Methods 276 (2017), 1–12.
[37] T.A.B. Snijders, The degree variance: an index of graph heterogeneity, Social Networks 3 (1981), no. 3, 163–174.
[38] R. Todeschini and V. Consonni, Handbook of Molecular Descriptors, 2nd ed., Wiley–VCH, Weinheim, 2009.
[39] N. Trinajstić, Chemical Graph Theory, CRC Press, Boca Raton, 1992.
[40] S. Yousaf, A.A. Bhatti, and A. Ali, A note on the modified Albertson index, Util. Math. (to appear).
Communications in Combinatorics and Optimization
Volume 5, Issue 2
December 2020
Pages 169-178

Files

Share

How to cite

Statistics