Abstract
Let G be a simple connected non-trivial graph of order n, size m, and vertex degree sequence (\(d_1, d_2,\ldots , d_n\)). The first Zagreb index \(M_1\), forgotten index F and inverse degree ID are the graph invariants defined as \(M_1(G)=\sum _{i=1}^n d_i^2\), \( F(G) = \sum _{i=1}^n d_i^3\) and \(ID(G)=\sum _{i=1}^n \frac{1}{d_i}\), respectively. A graph is said to be regular if all of its vertices have the same degree and otherwise, it is called a nonregular graph. For the quantitative topological characterization of the nonregularity of graphs, the graph invariants \(s(G)=\sum _{i=1}^n\left| d_i-\frac{2m}{n}\right| \) and \(Var(G)= \frac{1}{n}\sum _{i=1}^n \left( d_i - \frac{2m}{n} \right) ^2\) may be used. In this paper, some upper bounds for s(G) that reveal connections between s(G) and \(M_1(G)\), F(G), ID(G), Var(G) are obtained.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Throughout this paper, we assume that G is a connected simple graph with the vertex set \(V=\{v_1,v_2,\ldots ,v_n\}\) and size m where \(n\ge 2\). Also, it is supposed that \(\Delta =d_1\ge d_2\ge \cdots \ge d_n=\delta >0\) where \(d_i\) denotes the degree of the vertex \(v_i\in V\).
A graph invariant, or a topological index in chemical graph theory, is a numeric quantity associated with a graph which remains unchanged under graph isomorphism. A large number of topological indices have been defined in terms of vertex degrees.
The first Zagreb index, \(M_1\), defined [18] below, is actually one of the most thoroughly studied vertex-degree-based topological indices:
A modification of the first Zagreb index, defined as the sum of third powers of vertex degrees, that is
was first time encountered in 1972, in the paper [18], but was eventually disregarded. Recently, it was re-considered in [14] and named the forgotten index.
The inverse degree of a graph G, with no isolated vertices, is defined [12] as
The inverse degree first attracted attention through conjectures of the computer program Graffiti [12]. More details about the first Zagreb index, forgotten topological index and inverse degree can be found in the recent survey [3], where the mathematical properties of these indices have been summarized.
The graph G is said to be regular if \(d_1=d_2=\cdots =d_n\). A non-negative graph invariant I(G) is said to be a measure of irregularity if the following property holds: \(I(G) =0\) if and only if G is regular. A number of different irregularity measures have been proposed in the literature. A relevant list of papers concerned with various irregularity measures, but hardly exhaustive, would include [1, 2, 4, 7, 9,10,11, 16, 17, 20, 30, 32, 36, 37]. Among these irregularity measures, here, we mention only two that are of interest for the present study. The first one is the variance of the vertex degrees, proposed by Bell [4]. This irregularity measure for the graph G is defined as
Needless to say, \(\frac{2m}{n}\) is the average degree of G, which is equal to \(\frac{1}{n}\sum _{i=1}^n d_i\). The second one is the degree deviation, introduced by Nikiforov [32]. The degree deviation of the graph G is defined as
It needs to be mentioned here that the degree deviation of G is actually n times the Discrepancy [21, 24, 38] of G. Some mathematical properties of the degree deviation can be found in the survey [33] and papers [8, 15, 25, 32].
In the present work we determine upper bounds for s(G) that reveal connections between s(G) and \(M_1(G)\), F(G), ID(G) and Var(G). Needless to say, the purpose of our bounds is not to gain (approximate) numerical values of s(G) of particular graphs, since their exact values are easily obtainable by direct calculation.
2 Preliminaries
In this section, we recall some known results which will be used subsequently.
Nikiforov [32] mentioned the following upper bound on the degree deviation s(G) in terms of the graph invariant Var(G) and order of G
Inequality (1) was also derived in [38], where it was shown that the equality sign in (1) holds if and only there exists a constant c such that \(|d_i -\frac{2m}{n}|=c\) for every vertex \(v_i\in V\).
In [28], the following lower bound for the first Zagreb index \(M_1(G)\) was established
In [26] (see also [5, 6]), it was proven that the equality sign in (2) holds if and only if \(d_2=d_3=\cdots =d_{n-1}=\frac{\Delta +\delta }{2}\).
In [28] (see also [5, 6, 22, 29]), the following upper bound for \(M_1(G)\) was derived
where
The Jensen’s inequality [31] for real number sequences has the form mentioned in the following lemma.
Lemma 1
[31] Let \(p=(p_i)\) and \(a=(a_i)\) be positive and nonnegative real number sequences, respectively, where \(i=1,2,\ldots , n\). If r is a real number such that \(r\ge 1\) or \(r\le 0\) then
with equality if and only if either \(r=0\), or \(r=1\), or \(a_1=a_2=\cdots = a_n\). If \(0\le r\le 1\), then Inequality (4) is reversed.
Lemma 2
[34] Let \(x=(x_i)\) and \(a=(a_i)\) be positive real number sequences where \(i=1,2,\ldots ,n\). If r is a non-negative real number then it holds that
with equality if and only if \(r=0\) or \(\frac{x_1}{a_1}=\frac{x_2}{a_2}=\cdots =\frac{x_n}{a_n}\) .
3 Main results
Firstly, we establish an upper bound on degree deviation s(G) in terms of graph invariants n, m, \(\Delta \), \(\delta \) and Var(G).
Theorem 1
For \(n\ge 2\), if G is a simple connected graph with order n, size m, minimum degree \(\delta \), maximum degree \(\Delta \) and variance of vertex degrees Var(G) then
Equality in (6) holds if and only if there exists a constant “c” such that \(\left| d_i-\frac{2m}{n} \right| =c\) for every \(i\in \{2,3,\ldots ,n\}\) or for every \(i\in \{1,2,\ldots ,n-1\}\).
Proof
For \(r=2\), \(p_i=1\), \(i=2,3,\ldots ,n\), the Inequality (4) can be rewritten as
For \(a_i=\left| d_i-\frac{2m}{n} \right| \), \(i=2,3,\ldots ,n\), the above inequality becomes
that is
Using the relation
in (8), we get
In a similar way, starting with the inequality
we obtain
From Inequalities (9) and (10), Inequality (6) follows.
Now, we consider the equality case in (6). We note that the equality sign in (7) holds if and only if \(a_2=a_3=\cdots =a_n\), which implies that the equality sign in (9) holds if and only if there exist a constant \(c'\) such that \(\left| d_i-\frac{2m}{n} \right| =c'\) for every \(i\in \{2,3,\ldots ,n\}\). Similarly, the equality sign in (10) holds if and only if there exists a constant \(c''\) such that \(\left| d_i-\frac{2m}{n} \right| =c''\) for every \(i\in \{1,2,\ldots ,n-1\}\). Therefore, the equality sign in (6) holds if and only if there exists a constant c such that \(\left| d_i-\frac{2m}{n} \right| =c\) for every \(i\in \{2,3,\ldots ,n\}\) or for every \(i\in \{1,2,\ldots ,n-1\}\). \(\square \)
From (3), it follows that
By using Inequality (11) in (6), we get the next result.
Corollary 1
For \(n\ge 2\), if G is a simple connected graph with order n, size m, minimum degree \(\delta \) and maximum degree \(\Delta \) then
with equality if and only if G is a regular graph, where
Remark 1
Inequality (11) is stronger than the inequality \( Var(G)\le \frac{(\Delta -\delta )^2}{4}\,, \) which was proven in [23] (see also [13]).
Theorem 2
For \(n\ge 2\), if G is a simple connected graph with order n, size m, forgotten topological index F(G), inverse degree ID(G) and variance of vertex degrees Var(G) then
Equality sign in (12) holds if and only if there exists a constant “c” such that \(d_i\left| d_i-\frac{2m}{n} \right| =c\) for every \(i\in \{1,2,\ldots ,n\}\).
Proof
For \(r=1\), \(x_i=\left| d_i-\frac{2m}{n}\right| \), \(a_i=\frac{1}{d_i}\), \(i=1,2,\ldots ,n\), Inequality (5) transforms into
Now, using fact that
in (13), we arrive at Inequality (12).
Since \(r=1\ne 0\), equality sign in (5) holds if and only if \(\frac{x_1}{a_1}=\frac{x_2}{a_2}=\cdots =\frac{x_n}{a_n}\), which implies that the equality sign in (13), that is in (12), holds if and only if there exists a constant “c” such that \(d_i\left| d_i-\frac{2m}{n} \right| =c\) for every \(i\in \{1,2,\ldots ,n\}\). \(\square \)
From (2), it follows (see [19]) that \( Var(G)\ge \frac{(\Delta -\delta )^2}{2n}, \) and hence we have the next result as a direct consequence of Theorem 2.
Corollary 2
For \(n\ge 2\), if G is a simple connected graph with order n, size m, forgotten topological index F(G) and inverse degree ID(G) then
with equality if and only if G is a regular graph.
Theorem 3
For \(n\ge 2\), if G is a simple connected graph with order n, size m and inverse degree ID(G) then
with equality if and only if there is a constant “c” such that \(\frac{\left| d_i-\frac{2m}{n} \right| }{d_i}=c\) for every \(i\in \{1,2,\ldots ,n\}\).
Proof
For \(r=1\), \(x_i=\left| d_i-\frac{2m}{n}\right| \), \(a_i=d_i\), \(i=1,2,\ldots ,n\), Inequality (5) becomes
Now, using the relation
Since \(r=1\ne 0\), equality sign in (5) holds if and only if \(\frac{x_1}{a_1}=\frac{x_2}{a_2}=\cdots =\frac{x_n}{a_n}\), from which it follows that the equality sign in (15), that is in (14), holds if and only if there is a constant c such that \(\frac{\left| d_i-\frac{2m}{n} \right| }{d_i}=c\) for every \(i\in \{1,2,\ldots ,n\}\). \(\square \)
In [27] (see also [35]), it was proven that \( ID(G)\le \frac{n(\Delta +\delta )-2m}{\Delta \delta }\,. \) Therefrom we have the following corollary of Theorem 3.
Corollary 3
For \(n\ge 2\), if G is a simple connected graph with order n, size m, minimum degree \(\delta \) and maximum degree \(\Delta \) then
with equality if and only if G is a regular or semiregular \((\Delta ,\delta )\)-bipartite graph.
The proof of next result is fully analogous to that of Theorem 3 and hence omitted.
Theorem 4
For \(n\ge 2\), if G is a simple connected graph with order n, size m, minimum degree \(\delta \), maximum degree \(\Delta \) and inverse degree ID(G) then
with equality if and only if there is a constant “c” such that \(\frac{\left| d_i-\frac{2m}{n} \right| }{d_i}=c\) either for every \(i\in \{2,3,\ldots ,n\}\) or for every \(i\in \{1,2,\ldots ,n-1\}\).
Remark 2
It can be easily checked that Inequality (6) is stronger than (1) for nonregular graphs. However, Inequalities (1), (12) and (14) are incomparable; for example, Inequality (1) is stronger than Inequalities (12) and (14) if \(G\cong C_{n-1}+e\), (12) is stronger than (1) and (14) if \(G\cong P_n\), and Inequality (14) is stronger than (1) and (12) if \(G\cong K_{1,n-1}\), where \(C_{n-1}+e\) is the graph obtained from the cycle graph on \(n-1\) vertices by adding an edge.
References
Abdo, H., Brandt, S., Dimitrov, D.: The total irregularity of a graph. Discret Math. Theor. Comput. Sci. 16, 201–206 (2014)
Albertson, M.O.: The irregularity of graph. Ars Comb. 46, 219–225 (1997)
Ali, A., Gutman, I., Milovanović, E., Milovanović, I.: Sum of powers of the degrees of graphs: extremal results and bounds. MATCH Commun. Math. Comput. Chem. 80, 5–84 (2018)
Bell, F.K.: A note on the irregularity of graphs. Linear Algebra Appl. 161, 45–54 (1992)
Borovićanin, B., Das, K.C., Furtula, B., Gutman, I.: Bounds for Zagreb indices. MATCH Commun. Math. Comput. Chem. 78, 17–100 (2017)
Borovićanin, B., Das, K.C., Furtula, B., Gutman, I.: Zagreb indices: bounds and extremal graphs. In: I. Gutman, B. Furtula, K.C. Das, E. Milovanović, I. Milovanović (eds) Bounds in Chemical Graph Theory–Basics, Mathematical Chemistry Monographs, MCM 19, Univ. Kragujevac, Kragujevac, pp. 67–153. (2017)
Collatz, L., Sinogowitz, U.: Spektren endlicher Graphen. Abh. Math. Sem. Univ. Hamburg 21, 63–77 (1957)
Criado, R., Flores, J., del Amo, A.G., Romance, M.: Centralities of a network and its line graph: an analytical comparison by means of their irregularity. Int. J. Comput. Math. 91, 304–314 (2014)
Dimitrov, D., Réti, T.: Graphs with equal irregularity indices. Acta Polytechn. Hung. 11, 41–57 (2014)
Edwards, C.S.: The largest vertex degree sum for a triangle in a graph. Bull. London Math. Soc. 9, 203–208 (1977)
Elphick, C., Wocjan, P.: New measures of graph irregularity. El. J. Graph Theory Appl. 2(1), 52–65 (2014)
Fajtlowicz, S.: On conjectures on Graffiti-II. Congr. Numer. 60, 187–197 (1987)
Fath-Tabar, G.H.: Old and new Zagreb indices of graphs. MATCH Commun. Math. Comput. Chem. 65, 79–84 (2011)
Furtula, B., Gutman, I.: A forgotten topological index. J. Math. Chem. 53, 1184–1190 (2015)
Goldberg, F.: New results on eigenvalues and degree deviation, arXiv:1403.2629 [math.CO] (2014)
Gutman, I., Furtula, B., Elphick, C.: Three new/old vertex-degree-based topological indices. MATCH Commun. Math. Comput. Chem. 72, 617–632 (2014)
Gutman, I.: Irregularity of molecular graphs. Kragujevac J. Sci. 38, 71–81 (2016)
Gutman, I., Trinajstić, N.: Graph theory and molecular orbitals. Total \(\pi \)-electron of alternant hydrocarbons. Chem. Phys. Lett. 17, 535–538 (1972)
Gutman, I., Das, K.C., Furtula, B., Milovanović, E., Milovanović, I.: Generalizations of Szőkefalvi Nagy and Chebyshev inequalities with applications in spectral graph theory. Appl. Math. Comput. 313, 235–244 (2017)
Hamzah, A., Réti, T.: An analogue of Zagreb index inequality obtained from graph iregularity measures. MATCH Commun. Math. Comput. Chem. 72, 669–683 (2014)
Haviland, J.: On irregularity in graphs. Ars Combin. 78, 283–288 (2006)
Hosamani, S.M., Basavanagoud, B.: New upper bounds for the first Zagreb index. MATCH Commun. Math. Comput. Chem. 74, 97–101 (2015)
Izumino, S., Mori, H., Seo, Y.: On Ozeki’s inequality. J. Ineq. Appl. 2, 235–253 (1998)
Lawrence, C.J., Tizzard, K., Haviland, J.: Disease-spread and stochastic graphs. In: Proceedings of International Conference on Social Networks, London, pp. 143–150. (1995)
Liu, L., Kang, L., Shan, E.: On the irregularity of uniform hypergraphs. Eur. J. Combin. 71, 22–32 (2018)
Mansour, T., Rostami, M.A., Suresh, E., Xavier, G.B.A.: New sharp lower bounds for the first Zagreb index. Sci. Publ. State Univ. Novi Pazar Ser. A Appl. Math. Inform. Mech. 8(1), 11–19 (2016)
Milovanović, I.Ž., Ćirić, V.M., Milentijević, I.Z., Milovanović, E.I.: On some spectral vertex and edge degree-based graph invariants. MATCH Commun. Math. Comput. Chem. 77, 177–188 (2017)
Milovanović, E.I., Milovanović, I.Ž.: Sharp bounds for the first Zagreb index and first Zagreb coindex. Miskolc Math. Notes 16, 1017–1024 (2015)
Milovanović, I.Ž., Milovanović, E.I.: Correcting a paper on first Zagreb index. MATCH Commun. Math. Comput. Chem. 74, 693–695 (2015)
Milovanović, I.Ž., Milovanović, E.I., Ćirić, V., Jovanović, N.: On some irregularity measures of graphs. Sci. Publ. State Univ. Novi Pazar Ser. A Appl. Math. Inform. Mech. 8(1), 21–34 (2016)
Mitrinović, D.S., Pečarić, J.E., Fink, A.M.: Classical and New Inequalities in Analysis. Kluwer Academic Publishers, Dordrecht (1993)
Nikiforov, V.: Eigenvalues and degree deviation in graphs. Linear Algebra Appl. 414, 347–360 (2006)
de Oliveira, J.A., Oliveira, C.S., Justel, C., de Abreu, N.M.M.: Measures of irregularity of graphs. Pesq. Oper. 33, 383–398 (2013)
Radon, J.: Theorie und Anwendungen der absolut odditiven Mengenfunktionen. Sitzungsber. Acad. Wissen. Wien 122, 1295–1438 (1913)
Rodriguez, J.M., Sanchez, J.L., Sigarreta, J.M.: CMMSE-on the first general Zagreb index. J. Math. Chem. 56(7), 1849–1864 (2018)
Réti, T., Toth-Loufer, F.: On the construction and comparison of graph irregularity indices. Kragujevac J. Sci 39, 68–88 (2017)
Réti, T.: Graph irregularity and a problem raised by Hong. Acta Polytechn. Hung. 15(6), 27–43 (2018)
Zhou, B.: New upper bounds for Laplacian energy. MATCH Commun. Math. Comput. Chem. 62, 553–560 (2009)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Ali, A., Milovanović, E., Matejić, M. et al. On the Upper Bounds for the Degree Deviation of Graphs. J. Appl. Math. Comput. 62, 179–187 (2020). https://doi.org/10.1007/s12190-019-01279-6
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12190-019-01279-6