1. Introduction

Throughout this paper, we consider finite connected undirected simple graphs. Let G be such a graph with n vertices and m edges. The degree of a vertex u is denoted by d(u). Especially, and are called as maximum and minimum degree of G, espectively. The degree of an edge is denoted by d(e) in G, which is defined by d(e) = d(u)+d(v)−2 for . Let denotes the complement of G, with the same vertex set such that two vertices u and v are adjacent in if and only if they are not adjacent in G.

The first and second Zagreb indices are defined as (for instance, see ^[9] and references cited therein)

Numerous papers were recorded in the literature regarding the mathematical and chemical properties on Zagreb indices and the surveys on Zagreb indices. For the recent outcomes on Zagreb indices, see ^[5] and references cited therein. In 2005, Li and Zheng ^[13] introduced the the generalized version of the first Zagreb index. For and G be any graph, it satisfies

(1.1)

In 2015, Fortula and Gutman ^[8] re-introduced the forgotten topological index:

Mathematical properties of the forgotten topological index is seen in ^{[4, 8, 11, 19]}. Miličević, Nikolić and Trinajstić ^[15] reformulated the first Zagreb index in terms of edge-degree instead of vertex-degree:

The first reformulated Zagreb index is simply the Zagreb index of its line graph L(G). The use of these descriptors in QSPR study was also discussed in their report ^[15]. In ^{[6, 11, 12, 17, 20]}, various properties, relations and bounds are also explored.

The inverse degree was first appeared through conjectures of the computer program Graffiti ^[7] denote by ID(G); with no isolated vertices defined by

The inverse degree is a special case formula at in (1.1). For the recent results of the inverse degree, see ^{[3, 18]}. In analogy, the inverse edge degree of a graph G with no isolated edges is defined by

This paper is organized as follows. In Section 2, we give some preliminaries and basic definitions that will be used throughout the paper. In Sections 3 and 4, we present lower and upper bounds on the first reformulated Zagreb index in terms of and respectively. Furthermore, (Refer Table 3- Table 6) we showed that our bounds have the smallest deviation from the first reformulated Zagreb index and superior than the existing bounds in the literature.

2. Preliminaries

As usual and denote a path, star and a cycle of order n, respectively. Let G and H be graphs. We denote the number of distinct subgraphs of the graph G which are isomorphic to H by In specific, G has vertices, edges and triangles. Let and be positive integers, then the double star is a tree on vertices obtained from the path by attaching pendent vertices to its one vertex, and pendent vertices to its other vertex.

GraphTea ^[1] is a software tool for graph problems with a focus on extracting information and visualization. It offers powerful ways to query or directly interact with properties of a particular instance of a graph problem. It is specially designed for the computational works on the topological indices.

To analyse and compare our results, we need to recall few classes of graphs:

•  The wheel is join of the graphs and

• The crown is obtained from the cycle by adjoining a pendant edge at each vertex of the cycle.

• The helm is obtained from the wheel graph by adjoining a pendant edge at each vertex of the cycle.

• The flower is obtained from the helm by joining each pendent vertex to the central vertex of the helm.

• A graph is called bidegreed if its vertex degree is either Δ or with

In 2010, Zhou and Trinajstić ^[20] obtained the following identity.

Proposition 2.1. Let G be a simple graph with n vertices and m edges. Then

(2.1)

Using the results from ^[4] without exaggeration, we obtain the following corollary for in terms of its subgraphs of G.

Corollary 2.2. Let G be a simple graph with n vertices and m edges. Then

3. Lower Bounds on the First Reformulated Zagreb Index

In 2012, Ilić and Zhou ^[11] proposed the following lower bound for .

Lemma 3.1. Let G be a simple graph with n vertices and m edges. Then

(3.1)

with equality if and only if G is regular.

Very recently in 2016, Milovanović, Dolićanin, Glogić ^[16] obtained the new lower bounds for in terms of and .

Lemma 3.2. Let G be a simple graph with vertices and m edges. Then

(3.2)

(3.3)

equality holds if and only if G is a regular.

Remark 3.3. In 2015, Fortula and Gutman ^[8] have given the following lower bounds for Let G be a graph with m edges. Then

(3.4)

(3.5)

Note that, the equality of (3.4) holds if and only if G is regular. It is easy to see that, the inequality (3.2) can be obtained from (2.1) by using (3.4).

In analogy, one can propose a lower bound for using (3.5). But in 2012, De ^[6] obtained the following inequality.

Lemma 3.4. Let G be a simple graph with vertices and m edges. Then

(3.6)

equality holds if and only if G is a regular.

In 2010, Zhou and Trinajstić ^[19] proposed the following inequality in the context of general sum connectivity.

Lemma 3.5. Let G be a graph with edges. If then and if or then and either equality holds if and only if d(u) + d(v) is a constant for any edge uv.

Note that, for = 2 in Lemma 3.5 turns (3.5) as its special case. Also from Lemma 3.5, it is clear that the equality of (3.6) holds if and only if d(u) + d(v) is a constant for any edge uv: In addition, from ^[8], it is easy to see that (3.2) and (3.6) are incomparable.

Now, we are ready to present our lower bounds on in terms of and .

Theorem 3.6. Let G be a simple graph with n vertices and m edges, then

(3.7)

equality holds if and only if G is regular.

Proof. Consider be the non-negative weights, then we have the weighted version of Cauchy-Schwartz inequality

(3.8)

Since is non-negative, we assume that such that Thus

(3.9)

Set and for all in the above, we get

The inequality (3.7) is obtained from the above inequality and equality (2.1) and the equality holds if and only if G is regular.

Theorem 3.7. Let G be a simple graph with n vertices and m edges, then

(3.10)

equality holds if and only if G is regular.

Proof. The proof follows from the same terminology of Theorem 3.6 by choosing and for all

Remark 3.8. For every simple graph G, the lower bound in (3.10) is always better than the lower bound in (3.7). For this, we have to show that

(3.11)

By fixing and in (3.9), we achieve our required claim and the equality holds if and only if G is regular. Therefore inequality (3.10) is stronger than (3.7) and (3.7) is stronger than (3.2).

Remark 3.9. On the other hand, the lower bounds in (3.6) and (3.10) are incomparable. For Helm the lower bound in (3.10) is better than (3.6) and for the Flower the lower bound in (3.6) is better than (3.10). In addition for the Crown both the lower bounds coincides together, other than the equality case.

Next, we need to improve the lower bound (3.6). For which we need the following inequality which relates the first Zagreb index, second Zagreb index and the forgotten topological index.

Theorem 3.10. Let G be a simple graph with no isolated edges, then

(3.12)

equality holds if and only if d(u) + d(v) is a constant for any edge uv.

Proof. Considering the weighted version of Cauchy-Schwartz inequality from (3.8) with the assumption such that and by setting and for all we get

expanding, we have

and the equality holds if and only if d(u) + d(v) is a constant for any edge uv, which completes our claim.

Corollary 3.11. With the assumptions in Theorem 3.10, we have

(3.13)

equality holds if and only if d(u) + d(v) is a constant for any edge uv.

Remark 3.12. Still the lower bound in (3.10) and (3.13) are incomparable. Consider the Helm , for which the lower bound in (3.10) is finer than (3.13) and for the complement the lower bound in (3.13) is finer than (3.10).

Our next interest is to reduce the deviation for the lower bounds from the first reformulated Zagreb index. To achieve our goal, either we need to fit some good lower bounds for or some good upper bounds for in the equality (2.1).

In 2011, Ilić and Liu ^[10] proposed a new upper bound for the first Zagreb index and proved that it has the smallest deviation from the first Zagreb index.

Lemma 3.13. Let G be a simple regular graph with n vertices and m edges, with a vertices of maximum degree and b vertices of minimum degree Then

(3.14)

equality holds if and only if the vertex degrees are equal to or .

Thus we can state the following result.

Corollary 3.14. With the assumptions in Lemma 3.13, we have

(3.15)

To the best knowledge of the authors, still now in the literature (3.14) is superior upper bound for the first Zagreb index . This motivates us to present the new upper bound which is stronger than (3.14) and which leads to be the better lower bound for the first reformulated Zagreb index .

Theorem 3.15. Let G be a simple graph with n non-isolated vertices and m edges, with a vertices of maximum degree and b vertices of minimum degree Then

(3.16)

equality holds if and only if the vertex degrees are equal to or .

Proof. Let and be two sequences with the property for and be any sequence of positive real numbers, it holds

Since is a positive sequence, choose such that and by setting and and adding over the vertices by restricting we have

(3.17)

expanding the above inequality gives the required result with equality if and only if or This completes the proof.

The computational results for connected graphs on n = 3 to 9 vertices and connected trees on n = 10 to 20 vertices are provided in Table 1 and Table 2 respectively.

Table 1. Upper bound comparision of M₁²(G) for small graphs

Download as

PowerPoint Slide

Larger image(png format)

• Tables index

Veiw figure

View current table in a new window

View next table

Table 2. Upper bound comparison of M₁²(G) for small trees

Download as

PowerPoint Slide

Larger image(png format)

• Tables index

Veiw figure

View current table in a new window

View previous table

View next table

In the group one of the Table 1 and Table 2, the first column represents the degree of the vertex n, the second column contains number of connected graphs (trees) on n vertices and the third one has the average value of the first Zagreb index . Next two groups of three columns represent the average value of the upper bound, the standard deviation

and the number of graphs with equality case.

On comparison of the computational results in Table 1 and Table 2, we observe it is coherent that the upper bound (3.16) has the least deviation from and stronger than (3.14).

Corollary 3.16. With the assumptions in Theorem 3.15, we have

(3.18)

equality holds if and only if the vertex degrees are equal to or .

In analogy, Table 3 - Table 4 conclude that the lower bound (3.18) has the least deviation from and so it is superior than the existing lower bounds.

Table 3. Lower bound comparison of EM₁²(G) for small graphs

Download as

PowerPoint Slide

Larger image(png format)

• Tables index

Veiw figure

View current table in a new window

View previous table

View next table

Table 4. Lower bound comparison of EM₁²(G) for small trees

Download as

PowerPoint Slide

Larger image(png format)

• Tables index

Veiw figure

View current table in a new window

View previous table

View next table

4. Upper Bounds on the First Reformulated Zagreb Index

In 2010, Zhou and Trinajstić ^[20] proposed the first upper bound for

Lemma 4.1. Let G be a graph on n vertices and edges. Then

(4.1)

equality holds if and only if any two non-adjacent vertices have equal degrees.

In 2012, Ilić and Zhou ^[11] obtained the following upper bound for

Lemma 4.2. Let G be a simple graph with n vertices and m edges. Then

(4.2)

equality holds if and only if G is a regular or bidegreed graph.

In the same time period, De ^[6] Proposed the following upper bounds for

Lemma 4.3. Let G be a simple graph with n vertices and m edges. Then

(4.3)

(4.4)

equality holds if and only if G is regular.

In 2016, Milovanović et. al. ^[16] obtained some new upper bounds for the first reformulated Zagreb index.

Lemma 4.4. Let G be a simple graph with vertices and m edges. Then

(4.5)

equality holds if and only if G is regular or Moreover,

(4.6)

(4.7)

equality holds if and only if G is regular.

Remark 4.5. The upper bounds in (4.2) and (4.3) are emerged from Diaz-metcalf inequality, by considering the vertex and edge degrees respectively. At first, it is easy to see that the bounds in (4.1) and (4.2) are always better than (4.3) and (4.4). Secondly, the upper bound (4.2) is always better than the upper bounds (4.5), (4.6) and (4.7), so we leave it to the fascinated reader. In addition, the bounds in (4.1) and (4.2) are incomparable. For Helm Graphs (4.2) is better than (4.1), and for the Flower graphs (4.1) is better than (4.2).

Next, we are ready to present our inequality that determines upper bound for the forgotten topological index in terms of and which leads to the upper bound for

Theorem 4.6. Let G be a simple graph with n non-isolated vertices and m edges, with a vertices of maximum degree Δ and b vertices of minimum degree Then

(4.8)

equality holds if and only if the vertex degrees are equal to or .

Proof. The proof follows the same terminology of Theorem 3.15, by the choice of setting and

Corollary 4.7. With the assumptions in Theorem 4.6, we have

(4.9)

equality holds if and only if the vertex degrees are equal to or .

Corollary 4.8. Let G be a simple graph with n vertices and m edges, with a vertices of maximum degree Δ and b vertices of minimum degree Then

(4.10)

equality holds if and only if the vertex degrees are equal to or .

Proof. The proof follows the same terminology of Theorem 3.15, by the choice of setting and and using the equality (2.1).

From Table 5-Table 6 (with same notations in Table 1-Table 2), our upper bound (4.10) has the small deviation from which concludes that (4.10) is the superior than the existing upper bounds.

We end the paper by remarking that the lower and upper bounds of is determined in terms of n; m; and . In addition, we presented the upper bound for the first Zagreb index and the forgotten topological index and with the assistance of computational results, we conclude that these inequalities are superior than the other bounds appeared in the literature so far.

Table 5. Upper bound comparison of EM₁²(G) for small graphs

Download as

PowerPoint Slide

Larger image(png format)

• Tables index

Veiw figure

View current table in a new window

View previous table

View next table

Table 6. Upper bound comparison of EM₁²(G) for small trees

Download as

PowerPoint Slide

Larger image(png format)

• Tables index

Veiw figure

View current table in a new window

View previous table

References

[1]	M. Ali Rostami, H. Martin Bucker and A. Azadi, Illustrating a Graph Coloring Algorithm Based on the Principle of Inclusion and Exclusion Using GraphTea, LNCS, Springer. 8719 (2014) 514-517.
	In article
[2]	A.R. Ashrafi, T. Došlić and A.Hamzeha, The Zagreb coindices of graph operations, Discrete Appl. Math. 158 (2010) 1571-1578.
	In article		View Article
[3]	M. Bianchi, A. Cornaro, J. L. Palacios, A. Torriero, New bounds of degree-based topological indices for some classes of c-cyclic graphs. Discrete App. Math. 184 (2015) 62-75.
	In article		View Article
[4]	G.B.A. Xavier, E. Suresh and I. Gutman, Counting relations for general Zagreb indices, Kragujevac J. Math. 38 (2014) 95-103.
	In article		View Article
[5]	K. C. Das, K. Xu and J. Nam, Zagreb indices of graphs, Front. Math. China 10 (2015) 567-582.
	In article		View Article
[6]	N. De, Some bounds of reformulated Zagreb indices, Appl. Math. Sci. 6 (2012) 5005-5012.
	In article
[7]	S. Fajtlowicz S, On conjectures of graffiti II, Congr. Numer. 60 (1987), 189-197.
	In article
[8]	B. Fortula and I. Gutman, A forgotten topological index, J. Math. Chem. 53 (2015) 1184-1190.
	In article		View Article
[9]	I. Gutman, B. Ruščić, N. Trinajstić and C. F. Wilcox, Graph theory and molecular orbitals, XII. Acyclic polyenes, J. Chem. Phys. 62 (1975) 3399-3405.
	In article		View Article
[10]	A. Ilić, M. Ilić and B. Liu, On the upper bounds for the first Zagreb index, Kragujevac Journal of Math. 35 (2011) 173-182.
	In article
[11]	A. Ilić and B. Zhou, On reformulated Zagreb indices, Discrete App. Math. 160 (2012) 204-209.
	In article		View Article
[12]	S. Ji, X. Li and B. Huo, On Reformulated Zagreb Indices with Respect to Acyclic, Unicyclic and Bicyclic Graphs, MATCH Commun. Math. Comput. Chem. 72 (2014) 723{732.
	In article
[13]	X. Li and J. Zheng, A unified approach to the extremal trees for different indices, MATCH Commun. Math. Comput. Chem. 54 (2005) 195-208.
	In article
[14]	T. Mansour and C. Song, The a and (a,b)- Analogs of Zagreb Indices and Coindices of Graphs, Intern. J. Combin. (2012) ID 909285.
	In article
[15]	A. Miličević, S. Nikolić and N. Trinajstić, On reformulated Zagreb indices, Mol. Divers. 8 (2004) 393-399.
	In article		View Article  PubMed
[16]	E.I. Milovanović, I.Ž. Milovanović, E.Ć. Dolićanin and E. Glogić, A note on the first reformulated Zagreb index, Appl. Math. Comp. 273 (2016) 16-20.
	In article		View Article
[17]	G. Su, L. Xiong, L. Xu and B. Ma, On the maximum and minimum first reformulated Zagreb index with connectivity bat most k, FILMAT 25 (2011) 75-83.
	In article		View Article
[18]	K. Xu and K.C. Das, Some extremal graphs with respect to inverse degree, Discrete App. Math. (2015).
	In article
[19]	B. Zhou and N. Trinajstić, On general sum-connectivity index, J. Math. Chem. 47 (2010) 210-218.
	In article		View Article
[20]	B. Zhou and N. Trinajstić, Some properties of the reformulated Zagreb indices, J. Math. Chem. 48 (2010) 714-719.
	In article		View Article