On a conjecture about degree deviation measure of graphs

Document Type : Research Paper


Department of Pure Mathematics, Faculty of Mathematical Sciences, University of Kashan, Kashan 87317-53153, I. R. Iran


Let $G$ be an $n-$vertex graph with $m$ vertices‎. ‎The degree deviation measure of $G$ is defined as‎ ‎$s(G)$ $=$ $\sum_{v\in V(G)}|deg_G(v)‎- ‎\frac{2m}{n}|,$ where $n$ and $m$ are the number of vertices and edges of $G$‎, ‎respectively‎. ‎The aim of this paper is to prove the Conjecture 4.2 of [J‎. ‎A‎. ‎de Oliveira‎, ‎C‎. ‎S‎. ‎Oliveira‎, ‎C‎. ‎Justel and N‎. ‎M‎. ‎Maia de Abreu‎, ‎Measures of irregularity of graphs‎, Pesq‎. ‎Oper.‎, ‎33 (2013) 383--398]‎. ‎The degree deviation measure of chemical graphs under some conditions on the cyclomatic number is also computed‎.


Main Subjects

[1] M. O. Albertson, The irregularity of a graph, Ars Combin., 46 (1997) 219–225.
[2] A. Ali, E. Milovanović, M. Matejić and I. Milovanović, On the upper bounds for the degree deviation of graphs, J.
Appl. Math. Comput., http://dx.doi.org/10.1007/s12190-019-01279-6.
[3] H. Abdo, S. Brandt and D. Dimitrov, The total irregularity of a graph, Discrete Math. Theor. Comput. Sci., 16
(2014) 201–206.
[4] A. Ghalavand, A. R. Ashrafi and I. Gutman, Extremal graphs for the second multiplicative Zagreb index, Bull. Int.
Math. Virtual Inst., 8 (2018) 369–383.
[5] I. Gutman and N. Trinajstić, Graph theory and molecular orbitals. Total π−electron energy of alternant hydrocar-
bons, Chem. Phys. Lett., 17 ( 1972) 535–538.
[6] J. A. de Oliveira, C. S. Oliveira, C. Justel and N. M. Maia de Abreu, Measures of irregularity of graphs, Pesq. Oper.,
33 (2013) 383–398.
[7] V. Nikiforov, Eigenvalues and degree deviation in graphs, Linear Algebra Appl., 414 (2006) 347–360.
[8] T. Réti and Á. Drégelyi-Kiss, On the generalization of harmonic graphs, Discerete Math. Lett., 1 (2019) 16–20.