Volume 21, Issue 1 (4-2026)
IJMSI 2026, 21(1): 85-105 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Ghalavand A, Réti T, Milovanović I Z, Ashrafi A R. Graph Irregularity Characterization with Particular Regard to Bidegreed Graphs. IJMSI 2026; 21 (1) :85-105
URL: http://ijmsi.ir/article-1-2183-en.html
URL: http://ijmsi.ir/article-1-2183-en.html
Abstract:
In this study, we are interested mainly in investigating the relations between two graph irregularity measures which are widely used for structural irregularity characterization of connected graphs. Our study is focused on the comparison and evaluation of the discriminatory ability of irregularity measures called degree deviation S(G) and degree variance V ar(G). We establish various upper bounds for irregularity measures S(G) and V ar(G). It is shown that Nikiforov’s inequality which is valid for connected graphs can be sharpened in the form of V ar(G) < S(G)/2. Among others, it is verified that if G is a bidegreed graph then the discrimination ability of S(G) and V ar(G) is considered to be completely equivalent.
Type of Study: Research paper |
Subject:
General
References
1. R. Ahlswede, G. O. H. Katona, Graphs with Maximal Number of Adjacent Pairs of Edges, Acta Mathematica Academiae Scientiarum Hungaricae, 32, (1978), 97-120. [DOI:10.1007/BF01902206]
2. A. Ali, E. Milovanovi'c, M. Mateji'c, I. Milovanovi'c, On the Upper Bounds for the Degreedeviation of Graphs, Journal of Applied Mathematics and Computing, 62, (2020), 179-187.
3. F. K. Bell, A Note on the Irregularity of a Graph, Linear Algebra and its Applications, 161, (1992), 45-54. [DOI:10.1016/0024-3795(92)90004-T]
4. R. Bhatia, C. Davis, A Better Bound on the Variance, The American Mathematical Monthly, 107, (2000), 353-357. [DOI:10.1080/00029890.2000.12005203]
5. B. Bollob'as, Modern Graph Theory, Graduate Texts in Mathematics, Springer Verlag, New York, 1998. [DOI:10.1007/978-1-4612-0619-4]
6. O. Bucicovschi, S. M. Cioabˇa, The Minimum Degree Distance of Graphs of Given Order and Size, Discrete Applied Mathematics, 156, (2008), 3518-3521. [DOI:10.1016/j.dam.2008.03.036]
7. S. M. Cioabˇa, Sums of Powers of the Degrees of a Graph, Discrete Mathematics, 306, (2006), 1959-1964. [DOI:10.1016/j.disc.2006.03.054]
8. J. A. de Oliveira, C. S. Oliveira, C. Justel, N. M. Maia de Abreu, Measures of Irregularity of Graphs, Pesquisa Operacional, 33, (2013), 383-398. [DOI:10.1590/S0101-74382013005000012]
9. T. Doˇsli'c, On Discriminativity of Zagreb Indices, Iranian Journal of Mathematical Chemistry, 3, (2012), 25-34.
10. L. Feng, L. Lu, D. Stevanoviæ, A Short Remark on Graphs with Two Main Eigenvalues, Applied Mathematics and Computation, 369, (2020), 124858. [DOI:10.1016/j.amc.2019.124858]
11. B. Furtula, I. Gutman, M. Dehmer, On Structure-sensitivity of Degree-based Topological Indices, Applied Mathematics and Computation, 219, (2013), 8973-8978. [DOI:10.1016/j.amc.2013.03.072]
12. A. Ghalavand, A. R. Ashrafi, On a Conjecture about Degree Deviation Measure of Graphs, Transactions on Combinatorics, 1, (2021), 1-8.
13. A. Ghalavand, A. R. Ashrafi, I. Gutman, Extremal Graphs for the Second Multiplicative Zagreb Index, Bulletin of the International Mathematical Virtual Institute, 8(2), (2018), 369-383.
14. C. Godsil, G. Royle, Algebraic Graph Theory, Springer-Verlag, New York, 2001. [DOI:10.1007/978-1-4613-0163-9]
15. I. Gutman, Irregularity of Molecular Graphs, Kragujevac Journal of Science, 38, (2016), 71-81. [DOI:10.5937/KgJSci1638071G]
16. I. Gutman, Degree-based Topological Indices, Croatica Chemica Acta, 86, (2013), 351-361. [DOI:10.5562/cca2294]
17. I. Gutman, On Discriminativity of Vertex-degree-based Indices, Iranian Journal of Mathematical Chemistry, 3, (2012), 95-101.
18. I. Gutman, K. C. Das, The First Zagreb Index 30 Years after, MATCH Communications in Mathematical and in Computer Chemistry, 50, (2004), 83-92.
19. I. Gutman, P. Hansen, H. M'elot, Variable Neighborhood Search for Extremal Graphs, 10. Comparison of Irregularity Indices for Chemical Trees, Journal of Chemical Information and Modeling, 45, (2005), 222-230. [DOI:10.1021/ci0342775]
20. E. M. Hagos, Some Results on Graph Spectra, Linear Algebra and its Applications, 356, (2002), 103-111. [DOI:10.1016/S0024-3795(02)00324-5]
21. A. Hamzeh, T. R'eti, An Analogue of Zagreb Index Inequality Obtained from Graph Irregularity Measures, MATCH Communications in Mathematical and in Computer Chemistry, 72, (2014), 669-683.
22. S. Hayat, J. H. Koolen, F. Liu, Z. Qiao, A Note on Graphs with Exactly Two Main Eigenvalues, Linear Algebra and its Applications, 511, (2016), 318-327. [DOI:10.1016/j.laa.2016.09.019]
23. B. Liu, I. Gutman, Upper Bounds for Zagreb Indices of Connected Graphs, MATCH Communications in Mathematical and in Computer Chemistry, 55, (2006), 439-448.
24. I. Z. Milovanovi'c, E. I. Milovanovi'c, V. ˇ Ciri'c, N. Jovanovi'c, On Some Irregularity Mea- 'sures of Graphs, Scientific Publications of the State University of Novi Pazar Series A: Applied Mathematics, Informatics and mechanics, 8, (2016), 21-34. [DOI:10.5937/SPSUNP1601021M]
25. D. S. Mitrinovi'c, P. M. Vasi'c, Analytic Inequalities, Springer-Verlag, Berlin-Heidelberg-New York, 1970.
26. V. Nikiforov, Eigenvalues and Degree Deviation in Graphs, Linear Algebra and its Applications, 414, (2006), 347-360. [DOI:10.1016/j.laa.2005.10.011]
27. T. R'eti, A. Ali, On the Variance-type Graph Irregularity Measures, Communications in Combinatorics and Optimization, 5, (2020), 169-178. [DOI:10.1016/j.comcom.2021.07.025]
28. T. R'eti, E. Bitay, Comparing Zagreb Indices for 2-walk Linear Graphs, MATCH Communications in Mathematical and in Computer Chemistry, 85, (2021), 313-328.
29. T. R'eti, D. Dimitrov, On Irregularity of Bidegreed Graphs, Acta Polytechnica Hungarica, 10, (2013), 117-134. [DOI:10.12700/APH.10.07.2013.7.9]
30. T. R'eti, I. Milovanovi'c, E. Milovanovi'c, M. Mateji'c, On Graph Irregularity Indices with Particular Regard to Degree Deviation, Filomat, 35(11), (2021), 3689-3701. [DOI:10.2298/FIL2111689R]
31. T. R'eti, E. T'oth-Laufer, On the Construction and Comparison of Graph Irregularity Indices, Kragujevac Journal of Science, 39, (2017), 53-75. [DOI:10.5937/KgJSci1739053R]
32. P. Rowlinson, The Main Eigenvalues of a Graph: A Survey, Applicable Analysis and Discrete Mathematics, 1, (2007), 445-471. [DOI:10.2298/AADM0702445R]
33. L. Shi, On Graphs with Given Main Eigenvalues, Applied Mathematics Letters, 22, (2009), 1870-1874. [DOI:10.1016/j.aml.2009.06.027]
34. D. Stevanovi'c, Spectral Radius of Graphs, Academic Press, Amsterdam, 2015.
35. D. B. West, Introduction to graph theory, Prentic-Hall, Upper Saddle River, NJ. 1996.
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
