# On the Reformulated Multiplicative First Zagreb Index of Trees and Unicyclic Graphs

Authors: Akbar Ali; Atif Nadeem; Zahid Raza; Wael W. Mohammed; Elsayed M. Elsayed
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

The multiplicative first Zagreb index of a graphH is defined as the product of the squares of the degrees of vertices of H. The line graph of a graph H is denoted by LH and is defined as the graph whose vertex set is the edge set of H where two vertices of LH are adjacent if and only if they are adjacent in H. The multiplicative first Zagreb index of the line graph of a graph H is referred to as the reformulated multiplicative first Zagreb index of H. This paper gives characterization of the unique graph attaining the minimum or maximum value of the reformulated multiplicative first Zagreb index in the class of all (i) trees of a fixed order (ii) connected unicyclic graphs of a fixed order.


---

## Body

## 1. Introduction

A numerical quantity of a graph that remains the same under graph isomorphism is known as a graph invariant. For a graphH, denote by VH and EH, its vertex set and edge set, respectively. For a vertex v∈VH, denote by dvH and NHv, the degree of v and the set of all those vertices of H that are adjacent to v, respectively. The members of NHv are known as neighbors of v. For u,v∈VG, the edge with its end-vertices u and v is denoted by uv and the degree of uv is defined as duH+dvH−2. In the following, we drop the symbol “H” from “dvH” whenever there is no confusion about the graph under consideration. Also, in the present paper, we consider only connected graphs. The notation and terminology used in this paper, but not defined here, can be found in standard (chemical) graph-theoretical books, such as [1–3].Denote byM1H the sum of the squares of the degrees of vertices of H, that is,(1)M1H=∑v∈VHdv2.The graph invariantM1, known as the first Zagreb index, was appeared in the first quarter of 1970s within a study of chemical modeling [4]. The first Zagreb index can be considered as one of the most studied graph invariants, especially in chemical graph theory [5–11].The line graph of a graphH is denoted by LH and is defined as the graph whose vertex set is the edge set of H where two vertices of LH are adjacent if and only if they are adjacent in H. The first Zagreb index of the line graph of a graph H is known as the reformulated first Zagreb index [12] of H, and for simplicity, it is denoted as EM1H. Thus,(2)EM1H=M1LH=∑uv∈EHdu+dv−22.Details about the mathematical properties of the reformulated first Zagreb index can be found in [13–16].The multiplicative version of the first Zagreb index is defined [17, 18] as(3)Π1H=∏v∈VHdv2.The multiplicative first Zagreb index also gained a considerable attention from researchers, and hence, many investigations on this graph invariant have been conducted; for example, see [19, 20] and the related references included therein. Here, it should be pointed out that the multiplicative first Zagreb index is actually the square of the well-known Narumi–Katayama index [21], see, for example, [22], for details about the Narumi–Katayama index.This paper is concerned with the graph invariantΠ1LH that is the product of the squares of the degrees of edges of H. We call the invariant Π1LH as the reformulated multiplicative first Zagreb index of H and denote it by Π1,eH for simplicity. Thus,(4)Π1,eH=Π1LH=∏uv∈EHdu+dv−22.Throughout this paper, whenever we consider a class of graphs of the same order, we assume that all the graphs of the considered class are pairwise nonisomorphic. A graph containing exactly one cycle is known as a unicyclic graph. By ann-vertex graph, we mean a graph of order n. For n≥4, denote by Tn the class of all n-vertex trees and let Un be the class of all n-vertex connected unicyclic graphs. In this paper, the unique graph having the maximum or minimum value of the reformulated multiplicative first Zagreb index is characterized from each of the classes Tn and Un for every fixed integer n greater than 3.


## 2. Reformulated Multiplicative First Zagreb Index of Trees

This section is concerned with the characterization of the unique graph attaining the maximum or minimum value of the reformulated multiplicative first Zagreb index over the class of all trees of a fixed ordern≥4.A vertex of degree one is called a pendent vertex. A nontrivial pathP:v1v2…vr in a graph G is said to be a pendent path if mindv1,dvr=1 and maxdv1,dvr≥3, and every other vertex (if exists) of P has degree 2. Two pendent paths having the same vertex of degree greater than 2 are known as adjacent pendent paths. By an (n,m)‐graph, we mean a graph of order n and size m.Lemma 1.
IfG is a connected (n,m)‐graph containing at least one pair of adjacent pendent paths, then there exists at least one connected (n,m)-graph G′ such that(5)Π1,eG′<Π1,eG.Proof.
Letvu1u2…uq and vw1w2…wr be two adjacent pendent paths in G having lengths q and r, respectively. Without loss of generality, we assume that q≥r. Let G′ be the graph deduced from G by deleting the edge w1v and inserting the edge uqw1 (see Figure 1). Throughout this proof, by du, we mean the degree of the vertex u∈VG=VG′ in G. By the definition of the reformulated multiplicative first Zagreb index, there exists a positive integer z such that(6)Π1,eG−Π1,eG′=zΓ1∏w∈NGv∖u1,w1dw+dv−22−Γ2∏w∈NGv∖u1,w1dw+dv−32,where(7)Γ1=dv−14,ifq=r=1,dv2dv−12,ifq>1andr=1,dv4,ifq>1andr>1,Γ2=dv−12,ifq=r=1,4dv−12,ifq>1andr=1,16dv−12,ifq>1andr>1.
From the inequalitydv>2 (which gives dv2>4dv−1, that is, dv4>16dv−12) and equation (6), it follows that(8)Π1,eG−Π1,eG′>0.Figure 1
The graph transformation used in the proof of Lemma1.Theorem 1.
Among all trees of a fixed ordern≥4, path Pn is the unique graph with the minimum value of Π1,e. In other words, if T is any tree of order n≥4, then(9)Π1,eT≥Π1,ePn,with equality if and only if T is isomorphic to the path graph Pn.Proof.
LetT∗ be a tree with the minimum value of Π1,e among all trees of a fixed order n≥4. We claim that T∗ is isomorphic to Pn. Contrarily, we assume that T∗ is not isomorphic to Pn. Then, T∗ contains at least two adjacent pendent paths, and hence by Lemma 1, there exists at least one tree T′ such that(10)Π1,eT∗>Π1,eT′,which contradicts the definition of T∗. Thus, T∗≅Pn.Lemma 2.
LetG be a connected (n,m)‐graph. Let uv∈EG be an edge such that it does not lie on any triangle of G and duG≥dvG≥2, and NGv=u,w1,w2,…,wp. If G′ is the graph formed from G by deleting the edges w1v,w2v,…,wpv and inserting the edges w1u,w2u,…,wpu, then(11)Π1,eG<Π1,eG′.Proof.
In this proof, bydx, we mean the degree of the vertex x∈VG=VG′ in G. By the definition of the reformulated multiplicative first Zagreb index, there exists a positive integer z such that(12)Π1,eG−Π1,eG′=z∏i=1pdv+dwi−22∏y∈NGu∖vdu+dy−22−∏i=1pdu+dwi+p−22∏y∈NGu∖vdu+dy+p−22.
Sincedv≤du, the right hand side of equation (12) is negative.Theorem 2.
Among all trees of a fixed ordern≥4, star graph Sn uniquely attains the maximum value of Π1,e. In other words, if T is any tree of order n≥4, then(13)Π1,eT≤Π1,eSn,with equality if and only if T is isomorphic to the star graph Sn.Proof.
LetT∗ be a tree with the maximum value of Π1,e among all trees of a fixed order n≥4. Let Δ be the maximum degree of T∗. We claim that T∗ is isomorphic to Sn. Contrarily, we assume that T∗ is not isomorphic to Sn. Then, Δ≤n−2, and hence by Lemma 2, there exists at least one n-vertex tree T′ such that(14)Π1,eT∗<Π1,eT′,which contradicts the definition of T∗. Thus, T∗≅Sn.


## 3. Reformulated Multiplicative First Zagreb Index of Unicyclic Graphs

This section is concerned with the maximum and minimum values of the reformulated multiplicative first Zagreb index over the class of all unicyclic graphs of a fixed order.Theorem 3.
Among all connected unicyclic graphs of a fixed ordern≥4, the cycle graph Cn attains uniquely the minimum value of Π1,e. In other words, if G is any connected unicyclic graphs of order n≥4, then(15)Π1,eG≥Π1,eCn,with equality if and only if T is isomorphic to Cn.Proof.
LetG∗ be a graph attaining the minimum value of Π1,e in the class of all connected unicyclic graphs of a fixed order n≥4. If G∗ contains at least two adjacent pendent paths, then by Lemma 1, there exists at least one connected unicyclic graph G′ of order n such that(16)Π1,eG>Π1,eG′,which is a contradiction to the definition of G∗. Thus, G∗ does not have any pair of adjacent pendent paths, which implies that the maximum degree of G∗ is at most 3.
We claim that the maximum degree ofG∗ is 2, that is, G∗≅Cn. Contrarily, assume that uu1u2…ur is a pendent path in G∗, where u has degree 3 and ur has degree 1. Let v be a neighbor of u different from u1. Let G″ be the graph formed from G∗ by deleting the edge uv and inserting the edge urv (see Figure 2). In the following, by dx, we mean the degree of the vertex x∈VG∗=VG″ in G∗. By the definition of the reformulated multiplicative first Zagreb index, there exists a positive integer z such that(17)Π1,eG∗−Π1,eG″=zΓ1∏w∈NG∗u∖u1,vdw+12−Γ2∏w∈NG∗u∖u1,vdw2,where(18)Γ1=4dv+12,ifr=1,9dv+12,ifr≥2,Γ2=4dv2,ifr=1,16dv2,ifr≥2.
Sincedv≤3, it holds that 9dv+12≥16dv2; this together with equation (17) implies that(19)Π1,eG∗−Π1,eG″>0,which is again a contradiction to the definition of G∗. Therefore, G∗≅Cn.Figure 2
The graph transformation used in the proof of Theorem3.Theorem 4.
Among all connected unicyclic graphs of a fixed ordern≥4, the graph obtained from the star Sn by adding an edge attains uniquely the maximum value of Π1,e. In other words, if G is any connected unicyclic graphs of order n≥4, then(20)Π1,eG≤Π1,eSn+,with equality if and only if T is isomorphic to Sn+, where Sn+ is the graph obtained from the star Sn by adding an edge.Proof.
LetG∗ be a graph attaining the maximum value of Π1,e in the class of all connected unicyclic graphs of a fixed order n≥4. From Lemma 2, it follows that the removal of all the vertices of degree 1 of G∗ results in C3 (the cycle of order 3), that is, G∗ is isomorphic to the graph G† depicted in Figure 3. By routine calculations, one gets(21)Π1,eG†=p1+12p1p2+12p2p3+12p3p1+p2+22p1+p3+22p2+p3+22,where p1+p2+p3=n−3. Without loss of generality, we assume that p1≥p2≥p3≥0. Thus, n−p2−p3−3≥p2≥p3, and hence, 2n−6/3≥p2+p3. Equation (21) is equivalent to(22)Π1,eG†=n−p2−p3−22n−p2−p3−3p2+12p2p3+12p3n−p2−12n−p3−12p2+p3+22,with the condition p2+p3≤2n−6/3. For a fixed integer n≥4, since the function f defined by(23)fy,z=n−y−z−22n−y−z−3y+12yz+12zn−y−12n−z−12y+z+22,with y≥z≥0 and y+z≤2n−6/3 is strictly decreasing in y and z, we conclude that the maximum value of Π1,eG† is attained if and only if p2=p3=0. Therefore, G† is isomorphic to the graph Sn+.Figure 3
The graphG† used in the proof of Theorem 4.



---

*Source: 3324357-2021-10-26.xml*