Bell's Degree Variance and Degree Deviation in Graphs: Analyzing Optimal Graphs Based on These Irregularity Measures

Barzegar, Hasan; Sayadi, Mohsen; Alikhani, Saeed; Ghanbari, Nima

doi:10.30473/coam.2025.73746.1288

Articles in Press

Document Type : Research Article

Authors

¹ Department of Mathematics‎, ‎Tafresh University‎, ‎39518-79611‎, ‎Tafresh‎, ‎Iran

² Department of Mathematical Sciences‎, ‎Yazd University‎, ‎89195-741‎, ‎Yazd‎, ‎Iran

³ Department of Mathematical Sciences‎, ‎Yazd University‎, ‎89195-741‎, ‎Yazd‎, ‎Iran.

10.30473/coam.2025.73746.1288

Abstract

An irregularity measure (IM) of a connected graph $G$ is defined as a non-negative graph invariant that satisfies the condition‎ ‎$IM(G) = 0$ if and only if $G$ is a regular graph‎. ‎Among the prominent degree-based irregularity measures‎ ‎are Bell's degree variance, denoted as $Var_B(G)$, and degree deviation‎, represented as $S(G)$. Specifically, they are defined by the equations $Var_B(G) = \frac{1}{n} \sum_{i=1}^{n} \left( d_i‎ - ‎\frac{2m}{n} \right)^2$ and‎ ‎$S(G)=\sum_{i=1}^n \left|d_i‎- ‎\frac{2m}{n}\right |$‎, ‎where $m$ is the number of edges and $n$ is the number of vertices in $G$‎. ‎ This paper studies the properties of Bell's degree-variance and degree deviation for acyclic, unicyclic, and cactus graphs‎. ‎ Our analysis shows how these measures relate to graph topology and structure, influencing the overall irregularity. Additionally, we identify and analyze optimal graphs that minimize both irregularity measures, providing insights into their implications for network design, data structure optimization, and real-world applications. This study contributes to the understanding of graph irregularity and offers a framework for future research into irregularity measures across different classes of graphs.

Keywords

Main Subjects

Control and Optimization

References

[1] Albertson, M.O. (1997). “The irregularity of a graph”, Ars Combinatoria, 46, 219-225, doi: 0fba1b3710f21f7208f71ce2d605c777966af7b2.

[2] Abdo, H., Brandt, S., and Dimitrov, D. (2014). “The total irregularity of graph”, Discrete Mathematics and Theoretical Computer Science, 16, 201-206, doi:10.46298/dmtcs.1263.

[3] Bell, F.K. (1992). “A note on the irregularity of a graph”, Linear Algebra and its Applications, 161, 45-54, doi:10.1016/0024-3795(92)90004-t.

[4] Borissevich, K., and Doslić, T. (2015). “Counting dominating sets in cactus chains”, Filomat, 29(8), 1847-1855, doi:10.2298/fil1508847b.

[5] Collatz, L., and Sinogowitz, U. (1957). “Spektren endlicher grafen”, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 21, 63-77, doi:10.1007/bf02941924.

[6] Diudea, M.V., Gutman, I., and Lorentz, J. (2001). “Molecular topology”, Nova, Huntington.

[7] Firouzian, S., and Adabitabar Firozja, M. (2016). “Fuzzy number-valued fuzzy graph”, Control and Optimization in Applied Mathematics, 1(2), 77-86.

[8] Furtula, B., Gutman, I., Vukićević, Z.K., Lekishvili, G., and Popivoda, G. (2015). “On an old/new degree-based topological index”, Bulletin: Classe des Sciences Mathématiques Et Naturelles, 148(40), 19-31.

[9] Ghalavand, A., Reti, T., Milovanovic, I.Z., and Ashrafi, A.R. (2022). “Graph irregularity characterization with particular regard to bidegreed graphs”, arXiv:2211.06744, doi:10.48550/arXiv.2211.06744.

[10] Ghanbari, N. (2022). “On the Graovac-Ghorbani and atom-bond connectivity indices of graphs from primary subgraphs”, Iranian Journal of Mathematical Chemistry, 13(1), 45-72, doi:10.22052/ijmc.2022.246079.1612.

[11] Ghanbari, N., and Alikhani, S. (2021). “Mostar index and edge Mostar index of polymers”, Computational and Applied Mathematics, 40, 260, doi:10.1007/s40314-021-01652-x.

[12] Gutman, I. (2016). “Irregularity of molecular graph”, Kragujevac Journal of Science, 38, 99-109, doi: 10.5937/kgjsci1638071g.

[13] Hamidi, M., Norouzi, K., and Rezaei, A. (2021). “On grey graphs and their applications in optimization”, Control and Optimization in Applied Mathematics, 6(2), 79-96, doi:10.30473/coam. 2022.61195.1181.

[14] Harary, F., and Uhlenbeck, G. E. (1953). “On the number of Husimi trees”, Proceedings of the National Academy of Sciences, 39, 315-322, doi:10.1073/pnas.39.4.315.

[15] Hosoya, H., and Balasubramanian, K. (1989). “Exact dimer statistics and characteristic polynomials of cacti lattices”, Theoretica Chimica Acta, 76, 315-329, doi: 10.1007/bf00529932.

[16] Husimi, K. (1950). “Note on Mayer’s theory of cluster integrals”, The Journal of Chemical Physics, 18, 682-684, doi:10.1063/1.1747725.

[17] Nikiforov, V. (2006). “Eigenvalues and degree deviation in graph”, Linear Algebra and its Applications, 414, 347-360, doi:10.1016/j.laa.2005.10.011.

[18] Riddell, R. J. (1951). “Contributions to the theory of condensation”, Ph.D. Thesis, University of Michigan, Ann Arbor.

[19] Tavakoli, M., and Rahbarnia, F. (2012). “Note on properties of first Zagreb index of graphs”, Iranian Journal of Mathematical Chemistry, 3, 1-5, doi:10.22052/ijmc.2012.5269.

[20] Yousef, S., and Naeem, A. (2024). “On the multiplicative reformulated First Zagreb index of n-vertex trees with respect to matching number”, Iranian Journal of Mathematical Chemistry, 15(3), 203-225, doi:10.22052/ijmc.2024.253967.1793.

[21] Zmazek, B. (2004). “The obnoxious center problem on weighted cactus graphs”, Discrete Applied Mathematics, 136, 377-386, doi:10.1016/s0166-218x(03)00452-9.

[22] Zmazek, B., and Zerovnik, J. (2003). "Computing the weighted Wiener and Szeged number on weighted cactus graphs in linear time”, Croatica Chemica Acta, 76(2), 137-143.

Bell's Degree Variance and Degree Deviation in Graphs: Analyzing Optimal Graphs Based on These Irregularity Measures

References

References

Articles in Press, Accepted Manuscript Available Online from 19 April 2025

Articles in Press, Accepted Manuscript
Available Online from 19 April 2025