# Some Upper Bounds on the First General Zagreb Index

Authors: Muhammad Kamran Jamil; Aisha Javed; Ebenezer Bonyah; Iqra Zaman
Journal: Journal of Mathematics
 (2022)

---

## Abstract

The first general Zagreb indexMγG or zeroth-order general Randić index of a graph G is defined as MγG=∑v∈Vdvγ where γ is any nonzero real number, dv is the degree of the vertex v and γ=2 gives the classical first Zagreb index. The researchers investigated some sharp upper and lower bounds on zeroth-order general Randić index (for γ<0) in terms of connectivity, minimum degree, and independent number. In this paper, we put sharp upper bounds on the first general Zagreb index in terms of independent number, minimum degree, and connectivity for γ. Furthermore, extremal graphs are also investigated which attained the upper bounds.


---

## Body

## 1. Introduction

LetG be a connected, simple, and finite graph with vertex set VG and edge set EG. The total number of elements in VG is the order of the graph, and the number of edges which are connected with vertex v is said to be the degree dv of the vertex v. A vertex v is isolated if it has zero degree. For nonadjacent vertices v and w, a vw-vertex cut is a subset R⊆VG\v,w where v and w are from different components of G−R and the smallest cardinality set of vertices which separates v and w is minimal vertex cut. A subset H⊆VG of nonadjacent vertices is called an independent set, and the largest cardinality set among all independent sets of G is the independent number. A set X⊆V is called clique if all the vertices in X are adjacent. If a smallest set of vertices V0 exists in a connected graph G whose deletion makes it disconnect, then V0 is said to be the vertex connectivity or simple connectivity of G.For a subsetC⊆VG, GC is an induced subgraph of G whose vertices are from C and edges are with both ends in C. A graph G is bipartite with Y1,Y2⊂VG such that Y1∩Y2=Φ, Y1∪Y2=VG, and every edge connects a vertex from Y1 to a vertex in Y2. A bipartite graph in which each vertex of Y1 is connected with each vertex of Y2 by an edge is called a complete bipartite graph. Let F1 and F2 be two vertex disjoint graphs; then, F1+F2 is a graph with the vertex set VF1∪VF2 and the edge set EF1∪EF2∪xy:x∈VF1,y∈VF2.A topological index is a number corresponding to a molecule obtained from the molecular structure of the molecule. This number helps to predict the chemical or physical properties of that molecule. Due to strong applications in chemistry and pharmacy, hundreds of degree-based topological indices have been introduced.The first Zagreb index of a graphG, M1G, is defined as [2](1)M1G=∑v∈VGdv2.This old and useful topological index helped in obtaining properties of the structure of molecules such as branching, ZE-isomerism, complexity, heterosystems,π-electron energy, and many more [3, 4]. The concept of the first general Zagreb index was introduced by Li and Zheng in [5], and it is defined as(2)MγG=∑v∈VGdvγ,whereγ is any nonzero real number. The first general Zagreb index has grabbed attention of many chemists and mathematicians. Liu and Liu discussed some properties of MγG in [6] related to different operations on graph such as edge moving, edge separating, and edge switching. In [7], the authors presented some inequalities involving different graph parameters. In [8], the authors calculated the first general Zagreb index of generalized F-sums graphs. We refer the readers to [1, 9–14] for further study about this topological index.First, we present an auxiliary lemma which is a direct consequence of the definition of the first general Zagreb index [15].Lemma 1.
Letx and y be two nonadjacent vertices of G; then, for γ>0, we have(3)MγG<MγG+xy.


## 2. Graphs with Given Connectivity and Minimum Degree

In this section, we provide an upper bound on the first general Zagreb index in terms of order, vertex connectivity, and minimum degree. LetΘn,t,δ be the set of all graphs on n vertices, t vertex connectivity, and δ minimum degree, where 1≤t≤δ≤n and δ≥2.Theorem 2.
LetG∈Θn,t,δ and t≤δ≤n−1, and for γ>1, we have(4)MγG≤tn−1γ+δ−t+1δγ+n−δ−1n+t−δ−2γ,and the equality holds if and only if G=Kt+Kδ−t+1∪Kn−δ−1.Proof.
Forn=t+1, we have t=δ=n−1; in other words, Θn,t,δ=Kt+1. Suppose that n≥t+2 and let K be the graph in Θn,t,δ with the maximum first general Zagreb index for γ>1. Let C⊂VK be the vertex cut with cardinality t. We will prove our result by proving the following claims.
Claim I.K−C consists of exactly two components.Proof.
On the contrary, suppose thatK−C consists of at least three components. S1 and S2 are two components of K−C; then, there will be x∈VS1 and y∈VS2 such that K+xy∈Θn,t,δ which is against the assumption of K because of Lemma 1. This completes the proof of Claim I.
Now assume thatVS1=n1 and VS2=n2. Clearly, δ≤dx≤n1+t−1 and δ≤dy≤n2+t−1 where n1,n2≥δ−t+1.
Claim II.KC∪VS1 and KC∪VS2 are cliques.Proof.
On the contrary, suppose thatKC∪VS1 is not a clique. Then, we have two cases.Case 1.
There are nonadjacent verticesu,v∈C∪VS1 such that K+uv∈Θn,t,δ, which contradicts the assumption of K because of Lemma 1, and we have MγK<MγK+uv.Case 2.
Otherwise, joining nonadjacent vertices inK will increase the minimum degree of G. Then, from the proof of Claim III, we have(5)MγK<MγKδ+Kn1∪Kn2≤MγKt+Kδ−t+1∪Kn−t−1,which again contradicts that K has the maximal first general Zagreb index because Kt+Kδ−t+1∪Kn−t−1∈Θn,t,δ. This completes the proof of Claim II.
From Claim II, forn1,n2≥1 and n1+n2, we suppose that K=Kt+Kn1∪Kn2.
Letϕx=xx+tγ−x+1x+t+1γ; then, ϕ′x=x+tγ−1x+xγ+t−x+t+1γ−1xγ+x+γ+t+1<0 for γ>1.This implies that ϕx is a decreasing function.
Claim III. We haven1=δ−t+1 or n2=δ−t+1.Proof.
On the contrary, suppose thatn1≥n2>δ−t+1; then, we have MγKt+Kn1∪Kn2−MγKt+Kn1+1∪Kn2−1=n1n1+tγ+n2n2+tγ−n1+1n1+t+1γ−n2−1n2+t−1γ<0. The last inequality is due to the fact that ϕx is a decreasing function for γ>1 and n1>n2−1. This implies that MγKt+Kn1∪Kn2<MγKt+Kδ−t+1∪Kn−δ−1 if n1,n2>minδ−t+1,n−t−1. This completes the proof of Claim III.
From Claims I, II, and III, we deduce thatK=Kt+Kδ−t+1∪Kn−δ−1, which proves the theorem.


## 3. Bipartite Graphs with Given Connectivity

LetΥn,t denote the set of bipartite graphs of order n and vertex connectivity t. Now we introduce a graph Knx obtained from the graph Kx,n−x−1 by joining a new vertex u to t vertices of degree x of Kx,n−x−1.Theorem 3.
LetG∈Υn,tand1≤t≤n−1. Then, forγ>1,(6)MγG≤maxφa,φband the equality holds if and only if eitherG=KnaorG=Knb, where(7)φx=tγ+tx+1γ+n−x−1−txγ+xn−x−1γ,a=n−12−2t+12n,b=n−12−2t+12n.Proof.
Note thatΥn,1=K1,n−1, so we consider 1<t≤n/2. Let K∈Υn,t be the graph with the maximum first general Zagreb index having a t-vertex cut set C. Let X,Y⊂VK such that X∪Y=VK. Furthermore, we have CX=C∩X and CY=C∩Y. The required result is obtained by proving the following claims.
Claim I.KC and KC∪C1 are complete bipartite graphs, where C1 is one of the components in K−C.Proof.
Suppose on the contrary thatKC or KC∪C1 is not a complete bipartite graph. Then, there are two nonadjacent vertices x,y in K and K+xy∈Υn,t. From Lemma 1, we know that MγK<MγK+xy which is against the maximality of K. Hence, KC and KC∪C1 are complete bipartite graphs.
Claim II. IfCX and CY are nonempty subsets of K, then K−C has exactly two components.Proof.
K−C has at least three components and C2 and C3 are two of these components. Then, there are two vertices x∈VC2∩X,y∈VC3∩Y such that K+xy∈Υn,t with C being a t-vertex cut of K+xy. By Lemma 1, we have a contradiction that K has the maximum first general Zagreb index.
Claim III. EitherCX is empty or CY is empty.Proof.
On the contrary, suppose thatSX and SY are nonempty sets; then, by Claim II, K−C has exactly two components named C2 and C3. Let x∈VC2∩X and y∈VC3∩X. Assume that a=dx≥dy=b>0 and NC3y=c>0.(i)
Now we construct a new graphG∗ from K as G∗=K−zy:z∈NC2y+zx:z∈NC2y. By the definition of the first general Zagreb index, we have MγG∗−MγK=a+cγ+b−xγ−aγ−bγ>0, and the last inequality can be seen by considering the function ϕx=x+cγ−xγ. ϕx is an increasing function for x>0 and γ>1, and we have a>b−c; this implies that ϕa>ϕb−c.(ii)
LetCY=t and consider arbitrary vertices z1,z2,…,zt−l∈Y−C. Now we construct a new graph G∗∗ from G1 by adding more edges between the vertices of X−y and Y and adding further edges yz1,yz2,…,yzt−l. Clearly, NG2y is the vertex cut with cardinality t; in other words, G∗∗∈Υn,t. From Lemma 1 and i of Claim III, we have MγG∗∗>MγK, which is a contradiction.
From above claim, we deduce thatC⊂X is the t-vertex cut of K.
Claim IV.K−C consists of an isolated vertex.Proof.
On the contrary, suppose that the componentsC2,C3 of K−C are complete bipartite graphs. Also, suppose that VC1=X1∪Y1 and VC2=X2∪Y2, where Xi⊂X,Yi⊂Y for i=1,2.
Without loss of generality, suppose thatC⊂X and y∈Y1. Construct a new graph H from K as H=K−yz:z∈X1+xz:x∈X−C,z∈B−y,xz∉EK. This implies that C is also a t-vertex cut of H and H∈Υn,t. Similar to Claim III i, we have MγH−MγK>0, which is against the maximality of the first general Zagreb index of K.
By definition of the first general Zagreb index, we have(8)MγKna=tγ+ta+1γ+n−a−1−taγ+an−a−1γ.


## 4. Graphs with Given Connectivity and Independent Number

Letλn,t,a be the set of graphs of order n, vertex connectivity t, and independent number a. In this section, we investigate the graph which gives the maximum general first Zagreb index from λn,t,a.Theorem 4.
LetG∈λn,t,a with a≥1 and 1≤t≤n−1. Then, for γ≥1, we have(9)MγG≤n−t−an−2γ+a−1n−aγ+tn−1γ+tγand the equality holds if and only if G=Kt+K1∪Kn−t−a+a−1K1.Proof.
Fora=2, this result has been discussed in [16]. So, we assume that 2<a≤n−1, and let K be the graph with the maximum first general Zagreb index in λn,t,a and C,D be the t-vertex cut and maximum independent sets of K, respectively. The following claims will prove our main result.
Claim I. LetC1 be one component of K−C,VC1=p,VC1−D=q and C−D=r; then, we have KC1=Kq+r−pK1,KC=Kr+t−rK1 and KC∪VC1=Kq+r∪t+p−q−rK1.Proof.
AsK has the maximum first general Zagreb index and by Lemma 1, we have K=KC+KVG−C. On the contrary, suppose that KC1≠Kq+r−qK1; this implies that we have vertices x,y∈VC1−D and z∈VC1∩D such that xy∉EK or xz∉EK. Furthermore, one can notice that K+xy,K+xz∈λn,t,a. By Lemma 1, we have a contradiction of the choice of K, which proves the claim.
Claim II.K−C contains exactly two components.Proof.
On the contrary, suppose thatK−C contains at least three components, and two of them are named as C2 and C3. Let x∈VC1−D,y∈VC2−D. Then, K+xy∈λn,t,r, and we have a contradiction on the maximality of K by Lemma 1.
Claim III. IfVC2≥VC3, then VC3=1.Proof.
of Claim III. On the contrary, we supposeVC3≥2. Furthermore, if VC3−D=ϕ, then VC3=1 as C3 is a connected component. Suppose that VC3−D≠ϕ; then, VC3−D≠ϕ. Otherwise, VC3∩D=ϕ, and choosing x∈VC3, we have that D∪x is an independent set which is a contradiction to the definition of D.
Letw∈VC3∩D, and we construct a new graph H as H=K−xw:x∈VC2−D+xy:x∈VC2−w,y∈VC2. Clearly, D is the maximal independent set, and C is the minimal vertex cut set of K; H∈λn,t,a.
Letx∈VK−C−w and w∈VC2−D; then we have dKx<dHx. By applying the definition of Mγ on K and H, we obtain MγK−MγH<dHwγ+dHvγ−dKwγ−dKvγ<0 which is against the choice of K.
From Claims I, II, and III, we haveK∈G∗:G∗=Kn−a+a−1K1∪w∪z−iw:zi∈C,i=1,2,…,t, where w is an isolated vertex of K−C. Let C∩D=p; then,(10)MγG∗=pn−a+1γ+a−p−1n−aγ+t−pn−1γ+n−a−t+pn−2γ+tγ,=a−1n−aγ+n−an−2γ+tγ+tn−1γ−n−2γ+pn−a+1γ−n−aγ−n−1γ+n−2γ.
LetA=n−a+1γ−n−aγ−n−1γ+n−2γ. Consider the function gx=n−x+1γ−n−xγ for x≥1. As g′x<0, gx is a decreasing function for γ>1. This implies that A≤nγ−2n−1γ+n−2γ<0, and the last inequality is due to Jensen’s inequality. Hence, (1) attains its maximum value for p=0; in other words, for K=Kt+K1∪Kn−t−1+a−1K1, the first general Zagreb index attains its maximum value for γ>1.



---

*Source: 8131346-2022-01-12.xml*