# An Approach to the Extremal Inverse Degree Index for Families of Graphs with Transformation Effect

Authors: Muhammad Asif; Muhammad Hussain; Hamad Almohamedh; Khalid M. Alhamed; Sultan Almotairi
Journal: Journal of Chemistry
 (2021)

---

## Abstract

The inverse degree index is a topological index first appeared as a conjuncture made by computer program Graffiti in 1988. In this work, we use transformations over graphs and characterize the inverse degree index for these transformed families of graphs. We established bonds for different families ofn-vertex connected graph with pendent paths of fixed length attached with fully connected vertices under the effect of transformations applied on these paths. Moreover, we computed exact values of the inverse degree index for regular graph specifically unicyclic graph.


---

## Body

## 1. Introduction and Preliminary Results

Graph theory has many applications in chemistry, physics, computer sciences, and other applied sciences. Topological indices are graph invariants used to study the topology of graphs. Along with the computer networks, graph theory considers as a powerful tool in other areas of research, such as in coding theory, database management system, circuit design, secret sharing schemes, and theoretical chemistry [1]. Cheminformatics is the combination of technology, graph theory, and chemistry. It develops a relationship between structure of organic substances and their physiochemical properties through some useful graph invariants with the help of their associated molecular graph. The molecular graph is the combination of vertices and edges which are representatives of atoms and bonds between atoms of corresponding substance, respectively. Theoretical study of underlying chemical structure by some useful graph invariants is an attractive area of research in mathematical chemistry due to its effective applications in the QSAR/QSPR investigation [2, 3]. Topological indices among these invariants have special place and used to estimate the physiochemical properties of chemical compound. A topological index can be considered as a function which maps a graph to a real number.Throughout this work, we used standard notations,G=GV,E for graph, VG set of vertices, EG the set of edges, dvi degree of vertex vi (the number of edges incident to vi), Δ and δ be the maximum and minimum degrees of fully connected vertices, vertices with degree one are pendent vertices, and path attached with fully connected vertices taken as a pendent paths.In the last five decades, after the Wiener index, many topological indices had been introduced. Probably, the Randić connectivity index [4](1)RG=∑uv∈EG1dudv,is one of the best predictive invariants among these topological indices. The accuracy in predictability of indices is the main interest of researchers which leads them to purpose a new topological index.The zeroth-order general Randić indexRα0G=∑u∈VGduα was conceived by Li and Zheng in their work [5]. R1/20G=∑u∈VG1/du equivalent to Rα0G for α=−1/2. Hu et al. in [6] and others [7–10] characterize Rα0 for different values of α. For α=−1,R−10=ID is modified total adjacency index or inverse degree, first appears in the conjecture over computer program Graffiti [11]. The(2)IDG=∑v∈VG1dv=∑uv∈EGdu2+dv2du2dv2,for graphs without isolated vertices are well discussed in [12, 13]. Extremal characterization and bonds of IDG also discussed at some extent in [14–18]. For more detail, one can review survey [19].In this work, we investigated the effect of transformations over families of graphs forID and established inequalities for these transformed graphs. Graph transformations are very important in chemistry, computer designing, and animations. Moreover, we determined the exact value of ID for some major families of graphs under the effect of transformations over pendent paths.


## 2. Results and Discussion

In this section, we present some transformations over pendent paths. These have solid effect over increase and decrease ofIDG. Through out this work, we considered n0-vertex connected graph G0. Gkl be the graph G0 with k pendent paths of length l≥1 having order n=n0+kl with degree sequence d1=δ≤d2≤d3≤⋯≤Δ+1.


### 2.1. Graph Transformations

LetE′G⊂EG, the G1=G−E′G be subgraph obtained by removing edges of EG′, and G1′=G−V′G be the subgraph obtained by deleting vertices set V′G⊂VG along with their incident edges. We give following transformations using these techniques which have solid effect on IDG.


#### 2.1.1. TransformationA

Letwj∈VG0,dwj≥3, j=1,2,3,…,k≤n and wjuj1,uj1uj2,uj2uj3,…,ujl−1ujl be the pendent paths attached with fully connected vertex wj of G0 forms Gkl. Then,(3)AGkl=G1=G0−∑j=1kuj2uj3,uj3uj4,…,ujl−1ujl+∑j=1kwjuj2,uj2uj3,…,ujl−1ujl.Figure1 depicts successive application of transformation A as Ai, i=1,2,3,…,l−1.Figure 1
TransformationA.


#### 2.1.2. TransformationB

Letwj∈VG0,dwj≥3, j=1,2,3,…,k≤n and wjuj1,wjuj1,wjuj3,…,wjujl−i be the leafs attached with fully connected vertex wj of G. Then, for fixed vertex w1,(4)Gj′=G−uj1,uj2,uj3,…,ujl−q∪ujl−q−1ujl−q−2,ujl−q−2ujl−q−3,…,ujl−1ujl+w1uj1,w1uj1,w1uj3,…,w1ujl−q∪w1ujl−q−1,ujl−q−1ujl−q−2,ujl−q−2ujl−q−3,…,ujl−1ujl.Theorem 1.
LetG0 be the graph of order n1 with maximum degrees Δ and minimum δ. Then,(5)IDGkl≤IDAGkl,IDGkl≤IDBGkl.Proof.
LetGkl be the graph of order n=n1+kl, minimum degree δ, and maximum degree Δ+1. Gkl is the composition of G0 and k pendent paths of length l. In Gkl, there are at least k vertices of degree 1 and kl−1 having 2 and n1 vertices with degree dvs+1,δ≤dvs+1≤Δ+1:(6)IDGkl=∑s=1n−kl+11dvs+∑s=1k1dvs+1+k+kl−12.
The transformationA transforms k vertices from degree 2 to 1 and another k vertices from ds+1 to ds+2 which have an effect in ID as(7)IDAGkl=∑s=1n−kl+11dvs+∑s=1k1dvs+2+2k+kl−22.
So, from equations (6) and (7), we have(8)IDGkl−IDAGkl=∑s=1k1dvs+1−1dvs+2−k+k2=∑s=1k1dvs+1dvs+2−k2.
Replacedvs with minimum degree δ. It maximizes the term ∑s=1k1/dvs+1dvs+2, which implies(9)=∑s=1k1δ+1δ+2−k2=kδ+1δ+2−k2=k2−δ+1δ+2δ+1δ+2=k−δ2−3δδ+1δ+2.
It is clear from (9) that IDGkl−IDAGkl≤0. Hence,(10)IDGkl≤IDAGkl.
The transformationB shown in Figure 2 decreases the degree of one vertex and makes the same increase into the degree of fixed selected vertex:(11)IDBGkl=∑s=1n−kl+11dvs+∑s=1k−21dvs+1+1dvk+1dvk−1+2+kl−22+k.
So, from equations (6) and (11), we get(12)IDGkl−IDBGkl=∑s=1k1dvs+1−∑s=1k−21dvs+1−1dvk−1dvk−1+2,to maximize the fraction involved in above expression replace dvs,0≤s≤k with δ, and we get(13)IDGkl−IDBGkl=2δ+1−1δ−1δ+2=−2δ−2δ2−2δδ+1δ+2≤0.
The equation (13) implies(14)IDGkl≤IDBGkl.Figure 2
TransformationB for q=1.


#### 2.1.3. TransformationAij

The transformationAij is composition of Ai,0≤i≤l−1 and Bj,0≤j≤k−1 which is shown in Figure 3. Here, Ai,0≤i≤l−1 be the repetition of transformation A and Bj,0≤j≤k−1 be the repetition of transformation B.Figure 3
TransformationAij.For main results related to the transformationAij shown in Figure 3, we need to prove Propositions 1 and 2.Proposition 1.
Letg:N×W⟶Q defined as gη,ζ=1/η+ζ. Then,(1)
gη,ζ+1≥gη,ζ−1+1/2 for ζ≥1(2)
Forα,β≥0,gη,α+1β+1+gη,0≥gη,αβ+1+gη,β+1Proof.
(1) If transformationA applied on pendent path attached with vertex wj of G having degree η+ζ. The degree of vertex wj increased by one with change of vertex having degree 2 to leaf attached to wj. This change has effect on ID in the following way.
Letgη,ζ=1/η+ζ. Then,(15)gη,ζ+1−gη,ζ−1+12=1η+ζ+1−1η+ζ−1−12=12−1η+ζη+ζ−1.
It is clear from basic calculus that1/α≥1/α+β;β≥0. So,(16)=12−1η+ζη+ζ−1≥0,implies gη,ζ+ζ≥gη,ζ−1.
(2) The 2nd part of this preposition is related to the effect of transformationAij shown in Figure 3:(17)gη,α+1β+1+gη,0−gη,αβ+1+gη,β+1=1α+1β+η+1η−1α∗β+η−1β+η+1=α2β3+3α2β2+3α2β+α2+αβ3+2αβ2η+3αβ2+4αβη+3αβ+2aη+αηβ+η+1αβ+1+ηη+b+1≥0.
Thus,gη,α+1β+1+gη,0≥gη,αβ+1+gη,β+1.Proposition 2.
Letfη=1/η+3/2 and gη=1/η+1+2, then for η≥1, gη≥fη.Proof.
(18)gη−fη=1η+1+2−1η+32=1η+1−1η+12=2η−2η+1+ηη+12ηη+1=η−1+η2−12ηη+1≥0.
This fraction is nonnegative for allη≥1 which implies that gη≥fη.Theorem 2.
LetG be the graph of order n having p pendent vertices. Gkl is the graph having k pendent paths attached to the fully connected vertices with maximum degree of a vertex Δ+1. Then, for 0≤i≤l−1 and α≤β,(19)IDAiαGkl≤IDAiβGkl.Proof.
LetGkl be the graph with order n=n+kl, minimum degree δ, and maximum degree Δ+1. Using the fact of Aij over Gkl, we get(20)IDAijGkl=ki+1+kl−i+12+∑r=1k−j+11dvr+i+1+∑s=1n−p−k+j1dvs+1dvr+j+1i+1+p,for 1≤dr,ds≤Δ≤n−1 and 0≤i≤l−1,0≤j≤k−1. Then, for α≤β,(21)IDAiαGkl−IDAiβGkl=∑r=1k−α+11dvr+i+1+∑s=1n−p−k+α1dvs+1dvr+α+1i+1−∑r=1k−β+11dvr+i+1+∑s=1n−p−k+β1dvs+1dvr+β+1i+1=∑r=k−βk−α−11dvr+i+1−∑s=n−p−k+α+1n−p−k+β1dvs+i+1β−αdvr+i+1α+1dvr+i+1β+1.
So, by using Proposition1 and replacing Δ with dvr and δ with dvs, it is clear that Δ minimizes the positive terms and δ maximizes the negative term. After simplification, we get(22)=β−αδ−ΔΔ+i+1β+1Δ+i+1α+1+δ−ΔΔ+i+1i+1−i+12αΔ+Δ+i+1α+1β+1Δ+lα+1Δ+lβ+1δΔ+1.
It is clear that forα≤β, the nominator is a negative number and denominator is positive which implies that(23)IDAiαGkl−IDAiβGkl≤0.
Thus, forβ≥α,(24)IDAiαGkl≤IDAiβGkl.In the following theorem, we determined bonds ofID for graph Gkl under the effect of transformation Aij by using Propositions 1 and 2.Theorem 3.
LetG be the graph of order n having p pendent vertices. Gkl is the graph with maximum degree Δ+1 having order n+kl with k≤n−p of pendent paths of length l. Then, for IDAijGkl;0≤i≤l−1,0≤j≤k−1,(25)Δ+1Δl+1+2pΔ+n−p−1+2Δ2ΔΔ+1≤IDAijGkl.Equality holds forr-regular graph with i=0,j=0, and k=1. And(26)IDAijGkl≤δ+n−plδln−p+n−1+pδ+δn−pl+δδ,equality holds if under consideration graph is r-regular with k=n−p pendent paths of length l and i=l−1,j=k−1.Proof.
LetG be the graph having order n≥3 with 0≤p≤n−1 pendent vertices with minimum degree δ and maximum degree Δ. Gkl is the graph with maximum degree Δ+1 and maximum number of pendent paths k=n−p of length l. Then, by using equation (20),(27)IDAijGkl=ki+1+kl−i+12+∑r=1k−j+11dvr+i+1+∑s=1n−p−k+j1dvs+1dvr+j+1i+1+p,where 1≤dr,ds≤Δ≤n−1, and 0≤i≤l−1,0≤j≤k−1.
The order ofGkl is fixed. So, the increase in pendent paths causes to decrease their lengths l. This fact increases the number of pendent paths and decreases the vertices of degree two. So, Proposition 2 clears that IDAijGkl increases with the increase in k. It is clear from Theorems 1 and 2 and Propositions 1 and 2 that the least value of IDAijGkl was obtained by setting i,j=0, dr=ds=Δ, and k=1:(28)IDA00G1l≥1+1l−12+1−1Δ+1+n−p−1Δ+1Δ+1+p.
After simplification, we get(29)Δ+1Δl+1+2pΔ+n−p−1+2Δ2ΔΔ+1≤IDAijGkl,and equality holds in (28) for r-regular graph with the k=1 pendent path of length l and i=0,j=0.
Now again from (20), setting i=l−1,j=k−1,dr=ds=δ,k=n−p and using Proposition 1 and Theorems 1, 2, we get maximal value of IDAijGkl as(30)IDAl−1k−1Gkl≤n−pl−1+1+n−pl−l−1+12+∑s=1n−n−p+n−p−11δ+∑r=1n−p−n−p−1+11δ+l−1+1+1δ+n−p−1+1l−1+1+p.
After simplification, we get maximal value ofIDAijGkl as(31)IDAijGkl≤δ+n−plδln−p+n−1+pδ+δn−pl+δδ,in which equality holds for r-regular graph with k=n−p pendent paths of length l and i=l−1,j=k−1.
Inequalities (29) and (31) complete the proof.Theorem 4.
LetG be the graph without pendent vertices and Gkl for k>1 be the graph with maximum degree Δ+1. Then, for 0≤i≤l−1,0≤j≤k−1, the lower bond of IDAijGkl is(32)IDAijGkl≥Δ+1Δkl+1+2n−k+2kΔ2ΔΔ+1.Equality holds forr-regular graph with k pendent paths of length l and i = 0, j = 0.Proof.
LetG be the graph of order n without pendent vertices having minimum degree δ and maximum degree Δ. Gkl be the graph with maximum degree Δ+1 and k≥1 be the count of pendent paths of length l. Then, by using (20),(33)IDAijGkl=ki+1+kl−i+12+∑r=1k−j+11dvr+i+1+∑s=1n−k+j1dvs+1dvr+j+1i+1,where 1≤dr,ds≤Δ≤n−1, and 0≤i≤l−1,0≤j≤k−1. Using Propositions 1 and 2 and setting i,j=0,dr=ds=Δ, we get least value of IDAijGkl as IDA00Gkl:(34)IDA00Gkl=k+kl−12+k−1Δ+1+n−kΔ+1Δ+1.
After simplification, we get minimal value as(35)Δ+1Δkl+1+2n−k+2kΔ2ΔΔ+1≤IDAijGkl.
Equality for equation (3) holds for r-regular graph with k pendent paths of length l and i=0,j=0.Theorem 5.
LetG be the Δ-regular graph. IDAijGkl be the graph with k pendent paths of length l. Then, for 0≤i≤l−1,0≤j≤k−1:(36)IDAijGkl=Δ+i+1jΔ+i+12n−k+j+ki+l+12ΔΔ+i+1jk−j+Δk−j−1+ΔΔ+l2ΔΔ+i+1Δ+ji+1.Proof.
LetG be the Δ-regular graph and k be the count of pendent paths of length l. Then, Gkl is the graph with maximum degree Δ+1. Then, for 0≤i≤l−1,0≤j≤k−1, equation (20) takes the form(37)IDAijGkl=ki+1+kl−i+12+∑r=1k−j+11Δ+i+1+∑s=1n−k+j1Δ+1Δ+j+1i+1.
After simplification, we get required result:(38)IDAijGkl=Δ+i+1jΔ+i+12n−k+j+ki+l+12ΔΔ+i+1jk−j+Δk−j−1+ΔΔ+l2ΔΔ+i+1Δ+ji+1.In Corollary1, we determined exact values of ID for unicyclic graphs with k pendent paths of length l under transformation Aij. Figure 4(a) depicts transformed graph AijCn,kl for i=j=1, k=2 with fixed vertex w1 and Figure 4(b) with fixed vertex w2.Figure 4
TransformationAij effect over Gkl=Cn,2l: (a) transformed graph A11Cn,2l with fixed vertex w1; (b) transformed graph A11Cn,2l with fixed vertex w2.
(a)(b)Corollary 1.
LetCn be the unicyclic graph of order n. Cn,kl is the graph with k pendent paths of length l. Then, for 0≤i≤l−1,0≤j≤k−1,(39)IDAjGkl=2+i+1j3+i2n−k+j+ki+l+142+i+1jk−j+2k−j−1+22+l43+i2+ji+1.Proof.
Cn is the unicyclic graph of order n. Cn is 2-regular graph. Then, we get required result by replacing Δ by 2 in Theorem 5:(40)IDAjGkl=2+i+1j3+i2n−k+j+ki+l+142+i+1jk−j+2k−j−1+22+l43+i2+ji+1.


## 2.1. Graph Transformations

LetE′G⊂EG, the G1=G−E′G be subgraph obtained by removing edges of EG′, and G1′=G−V′G be the subgraph obtained by deleting vertices set V′G⊂VG along with their incident edges. We give following transformations using these techniques which have solid effect on IDG.


### 2.1.1. TransformationA

Letwj∈VG0,dwj≥3, j=1,2,3,…,k≤n and wjuj1,uj1uj2,uj2uj3,…,ujl−1ujl be the pendent paths attached with fully connected vertex wj of G0 forms Gkl. Then,(3)AGkl=G1=G0−∑j=1kuj2uj3,uj3uj4,…,ujl−1ujl+∑j=1kwjuj2,uj2uj3,…,ujl−1ujl.Figure1 depicts successive application of transformation A as Ai, i=1,2,3,…,l−1.Figure 1
TransformationA.


### 2.1.2. TransformationB

Letwj∈VG0,dwj≥3, j=1,2,3,…,k≤n and wjuj1,wjuj1,wjuj3,…,wjujl−i be the leafs attached with fully connected vertex wj of G. Then, for fixed vertex w1,(4)Gj′=G−uj1,uj2,uj3,…,ujl−q∪ujl−q−1ujl−q−2,ujl−q−2ujl−q−3,…,ujl−1ujl+w1uj1,w1uj1,w1uj3,…,w1ujl−q∪w1ujl−q−1,ujl−q−1ujl−q−2,ujl−q−2ujl−q−3,…,ujl−1ujl.Theorem 1.
LetG0 be the graph of order n1 with maximum degrees Δ and minimum δ. Then,(5)IDGkl≤IDAGkl,IDGkl≤IDBGkl.Proof.
LetGkl be the graph of order n=n1+kl, minimum degree δ, and maximum degree Δ+1. Gkl is the composition of G0 and k pendent paths of length l. In Gkl, there are at least k vertices of degree 1 and kl−1 having 2 and n1 vertices with degree dvs+1,δ≤dvs+1≤Δ+1:(6)IDGkl=∑s=1n−kl+11dvs+∑s=1k1dvs+1+k+kl−12.
The transformationA transforms k vertices from degree 2 to 1 and another k vertices from ds+1 to ds+2 which have an effect in ID as(7)IDAGkl=∑s=1n−kl+11dvs+∑s=1k1dvs+2+2k+kl−22.
So, from equations (6) and (7), we have(8)IDGkl−IDAGkl=∑s=1k1dvs+1−1dvs+2−k+k2=∑s=1k1dvs+1dvs+2−k2.
Replacedvs with minimum degree δ. It maximizes the term ∑s=1k1/dvs+1dvs+2, which implies(9)=∑s=1k1δ+1δ+2−k2=kδ+1δ+2−k2=k2−δ+1δ+2δ+1δ+2=k−δ2−3δδ+1δ+2.
It is clear from (9) that IDGkl−IDAGkl≤0. Hence,(10)IDGkl≤IDAGkl.
The transformationB shown in Figure 2 decreases the degree of one vertex and makes the same increase into the degree of fixed selected vertex:(11)IDBGkl=∑s=1n−kl+11dvs+∑s=1k−21dvs+1+1dvk+1dvk−1+2+kl−22+k.
So, from equations (6) and (11), we get(12)IDGkl−IDBGkl=∑s=1k1dvs+1−∑s=1k−21dvs+1−1dvk−1dvk−1+2,to maximize the fraction involved in above expression replace dvs,0≤s≤k with δ, and we get(13)IDGkl−IDBGkl=2δ+1−1δ−1δ+2=−2δ−2δ2−2δδ+1δ+2≤0.
The equation (13) implies(14)IDGkl≤IDBGkl.Figure 2
TransformationB for q=1.


### 2.1.3. TransformationAij

The transformationAij is composition of Ai,0≤i≤l−1 and Bj,0≤j≤k−1 which is shown in Figure 3. Here, Ai,0≤i≤l−1 be the repetition of transformation A and Bj,0≤j≤k−1 be the repetition of transformation B.Figure 3
TransformationAij.For main results related to the transformationAij shown in Figure 3, we need to prove Propositions 1 and 2.Proposition 1.
Letg:N×W⟶Q defined as gη,ζ=1/η+ζ. Then,(1)
gη,ζ+1≥gη,ζ−1+1/2 for ζ≥1(2)
Forα,β≥0,gη,α+1β+1+gη,0≥gη,αβ+1+gη,β+1Proof.
(1) If transformationA applied on pendent path attached with vertex wj of G having degree η+ζ. The degree of vertex wj increased by one with change of vertex having degree 2 to leaf attached to wj. This change has effect on ID in the following way.
Letgη,ζ=1/η+ζ. Then,(15)gη,ζ+1−gη,ζ−1+12=1η+ζ+1−1η+ζ−1−12=12−1η+ζη+ζ−1.
It is clear from basic calculus that1/α≥1/α+β;β≥0. So,(16)=12−1η+ζη+ζ−1≥0,implies gη,ζ+ζ≥gη,ζ−1.
(2) The 2nd part of this preposition is related to the effect of transformationAij shown in Figure 3:(17)gη,α+1β+1+gη,0−gη,αβ+1+gη,β+1=1α+1β+η+1η−1α∗β+η−1β+η+1=α2β3+3α2β2+3α2β+α2+αβ3+2αβ2η+3αβ2+4αβη+3αβ+2aη+αηβ+η+1αβ+1+ηη+b+1≥0.
Thus,gη,α+1β+1+gη,0≥gη,αβ+1+gη,β+1.Proposition 2.
Letfη=1/η+3/2 and gη=1/η+1+2, then for η≥1, gη≥fη.Proof.
(18)gη−fη=1η+1+2−1η+32=1η+1−1η+12=2η−2η+1+ηη+12ηη+1=η−1+η2−12ηη+1≥0.
This fraction is nonnegative for allη≥1 which implies that gη≥fη.Theorem 2.
LetG be the graph of order n having p pendent vertices. Gkl is the graph having k pendent paths attached to the fully connected vertices with maximum degree of a vertex Δ+1. Then, for 0≤i≤l−1 and α≤β,(19)IDAiαGkl≤IDAiβGkl.Proof.
LetGkl be the graph with order n=n+kl, minimum degree δ, and maximum degree Δ+1. Using the fact of Aij over Gkl, we get(20)IDAijGkl=ki+1+kl−i+12+∑r=1k−j+11dvr+i+1+∑s=1n−p−k+j1dvs+1dvr+j+1i+1+p,for 1≤dr,ds≤Δ≤n−1 and 0≤i≤l−1,0≤j≤k−1. Then, for α≤β,(21)IDAiαGkl−IDAiβGkl=∑r=1k−α+11dvr+i+1+∑s=1n−p−k+α1dvs+1dvr+α+1i+1−∑r=1k−β+11dvr+i+1+∑s=1n−p−k+β1dvs+1dvr+β+1i+1=∑r=k−βk−α−11dvr+i+1−∑s=n−p−k+α+1n−p−k+β1dvs+i+1β−αdvr+i+1α+1dvr+i+1β+1.
So, by using Proposition1 and replacing Δ with dvr and δ with dvs, it is clear that Δ minimizes the positive terms and δ maximizes the negative term. After simplification, we get(22)=β−αδ−ΔΔ+i+1β+1Δ+i+1α+1+δ−ΔΔ+i+1i+1−i+12αΔ+Δ+i+1α+1β+1Δ+lα+1Δ+lβ+1δΔ+1.
It is clear that forα≤β, the nominator is a negative number and denominator is positive which implies that(23)IDAiαGkl−IDAiβGkl≤0.
Thus, forβ≥α,(24)IDAiαGkl≤IDAiβGkl.In the following theorem, we determined bonds ofID for graph Gkl under the effect of transformation Aij by using Propositions 1 and 2.Theorem 3.
LetG be the graph of order n having p pendent vertices. Gkl is the graph with maximum degree Δ+1 having order n+kl with k≤n−p of pendent paths of length l. Then, for IDAijGkl;0≤i≤l−1,0≤j≤k−1,(25)Δ+1Δl+1+2pΔ+n−p−1+2Δ2ΔΔ+1≤IDAijGkl.Equality holds forr-regular graph with i=0,j=0, and k=1. And(26)IDAijGkl≤δ+n−plδln−p+n−1+pδ+δn−pl+δδ,equality holds if under consideration graph is r-regular with k=n−p pendent paths of length l and i=l−1,j=k−1.Proof.
LetG be the graph having order n≥3 with 0≤p≤n−1 pendent vertices with minimum degree δ and maximum degree Δ. Gkl is the graph with maximum degree Δ+1 and maximum number of pendent paths k=n−p of length l. Then, by using equation (20),(27)IDAijGkl=ki+1+kl−i+12+∑r=1k−j+11dvr+i+1+∑s=1n−p−k+j1dvs+1dvr+j+1i+1+p,where 1≤dr,ds≤Δ≤n−1, and 0≤i≤l−1,0≤j≤k−1.
The order ofGkl is fixed. So, the increase in pendent paths causes to decrease their lengths l. This fact increases the number of pendent paths and decreases the vertices of degree two. So, Proposition 2 clears that IDAijGkl increases with the increase in k. It is clear from Theorems 1 and 2 and Propositions 1 and 2 that the least value of IDAijGkl was obtained by setting i,j=0, dr=ds=Δ, and k=1:(28)IDA00G1l≥1+1l−12+1−1Δ+1+n−p−1Δ+1Δ+1+p.
After simplification, we get(29)Δ+1Δl+1+2pΔ+n−p−1+2Δ2ΔΔ+1≤IDAijGkl,and equality holds in (28) for r-regular graph with the k=1 pendent path of length l and i=0,j=0.
Now again from (20), setting i=l−1,j=k−1,dr=ds=δ,k=n−p and using Proposition 1 and Theorems 1, 2, we get maximal value of IDAijGkl as(30)IDAl−1k−1Gkl≤n−pl−1+1+n−pl−l−1+12+∑s=1n−n−p+n−p−11δ+∑r=1n−p−n−p−1+11δ+l−1+1+1δ+n−p−1+1l−1+1+p.
After simplification, we get maximal value ofIDAijGkl as(31)IDAijGkl≤δ+n−plδln−p+n−1+pδ+δn−pl+δδ,in which equality holds for r-regular graph with k=n−p pendent paths of length l and i=l−1,j=k−1.
Inequalities (29) and (31) complete the proof.Theorem 4.
LetG be the graph without pendent vertices and Gkl for k>1 be the graph with maximum degree Δ+1. Then, for 0≤i≤l−1,0≤j≤k−1, the lower bond of IDAijGkl is(32)IDAijGkl≥Δ+1Δkl+1+2n−k+2kΔ2ΔΔ+1.Equality holds forr-regular graph with k pendent paths of length l and i = 0, j = 0.Proof.
LetG be the graph of order n without pendent vertices having minimum degree δ and maximum degree Δ. Gkl be the graph with maximum degree Δ+1 and k≥1 be the count of pendent paths of length l. Then, by using (20),(33)IDAijGkl=ki+1+kl−i+12+∑r=1k−j+11dvr+i+1+∑s=1n−k+j1dvs+1dvr+j+1i+1,where 1≤dr,ds≤Δ≤n−1, and 0≤i≤l−1,0≤j≤k−1. Using Propositions 1 and 2 and setting i,j=0,dr=ds=Δ, we get least value of IDAijGkl as IDA00Gkl:(34)IDA00Gkl=k+kl−12+k−1Δ+1+n−kΔ+1Δ+1.
After simplification, we get minimal value as(35)Δ+1Δkl+1+2n−k+2kΔ2ΔΔ+1≤IDAijGkl.
Equality for equation (3) holds for r-regular graph with k pendent paths of length l and i=0,j=0.Theorem 5.
LetG be the Δ-regular graph. IDAijGkl be the graph with k pendent paths of length l. Then, for 0≤i≤l−1,0≤j≤k−1:(36)IDAijGkl=Δ+i+1jΔ+i+12n−k+j+ki+l+12ΔΔ+i+1jk−j+Δk−j−1+ΔΔ+l2ΔΔ+i+1Δ+ji+1.Proof.
LetG be the Δ-regular graph and k be the count of pendent paths of length l. Then, Gkl is the graph with maximum degree Δ+1. Then, for 0≤i≤l−1,0≤j≤k−1, equation (20) takes the form(37)IDAijGkl=ki+1+kl−i+12+∑r=1k−j+11Δ+i+1+∑s=1n−k+j1Δ+1Δ+j+1i+1.
After simplification, we get required result:(38)IDAijGkl=Δ+i+1jΔ+i+12n−k+j+ki+l+12ΔΔ+i+1jk−j+Δk−j−1+ΔΔ+l2ΔΔ+i+1Δ+ji+1.In Corollary1, we determined exact values of ID for unicyclic graphs with k pendent paths of length l under transformation Aij. Figure 4(a) depicts transformed graph AijCn,kl for i=j=1, k=2 with fixed vertex w1 and Figure 4(b) with fixed vertex w2.Figure 4
TransformationAij effect over Gkl=Cn,2l: (a) transformed graph A11Cn,2l with fixed vertex w1; (b) transformed graph A11Cn,2l with fixed vertex w2.
(a)(b)Corollary 1.
LetCn be the unicyclic graph of order n. Cn,kl is the graph with k pendent paths of length l. Then, for 0≤i≤l−1,0≤j≤k−1,(39)IDAjGkl=2+i+1j3+i2n−k+j+ki+l+142+i+1jk−j+2k−j−1+22+l43+i2+ji+1.Proof.
Cn is the unicyclic graph of order n. Cn is 2-regular graph. Then, we get required result by replacing Δ by 2 in Theorem 5:(40)IDAjGkl=2+i+1j3+i2n−k+j+ki+l+142+i+1jk−j+2k−j−1+22+l43+i2+ji+1.


## 2.1.1. TransformationA

Letwj∈VG0,dwj≥3, j=1,2,3,…,k≤n and wjuj1,uj1uj2,uj2uj3,…,ujl−1ujl be the pendent paths attached with fully connected vertex wj of G0 forms Gkl. Then,(3)AGkl=G1=G0−∑j=1kuj2uj3,uj3uj4,…,ujl−1ujl+∑j=1kwjuj2,uj2uj3,…,ujl−1ujl.Figure1 depicts successive application of transformation A as Ai, i=1,2,3,…,l−1.Figure 1
TransformationA.


## 2.1.2. TransformationB

Letwj∈VG0,dwj≥3, j=1,2,3,…,k≤n and wjuj1,wjuj1,wjuj3,…,wjujl−i be the leafs attached with fully connected vertex wj of G. Then, for fixed vertex w1,(4)Gj′=G−uj1,uj2,uj3,…,ujl−q∪ujl−q−1ujl−q−2,ujl−q−2ujl−q−3,…,ujl−1ujl+w1uj1,w1uj1,w1uj3,…,w1ujl−q∪w1ujl−q−1,ujl−q−1ujl−q−2,ujl−q−2ujl−q−3,…,ujl−1ujl.Theorem 1.
LetG0 be the graph of order n1 with maximum degrees Δ and minimum δ. Then,(5)IDGkl≤IDAGkl,IDGkl≤IDBGkl.Proof.
LetGkl be the graph of order n=n1+kl, minimum degree δ, and maximum degree Δ+1. Gkl is the composition of G0 and k pendent paths of length l. In Gkl, there are at least k vertices of degree 1 and kl−1 having 2 and n1 vertices with degree dvs+1,δ≤dvs+1≤Δ+1:(6)IDGkl=∑s=1n−kl+11dvs+∑s=1k1dvs+1+k+kl−12.
The transformationA transforms k vertices from degree 2 to 1 and another k vertices from ds+1 to ds+2 which have an effect in ID as(7)IDAGkl=∑s=1n−kl+11dvs+∑s=1k1dvs+2+2k+kl−22.
So, from equations (6) and (7), we have(8)IDGkl−IDAGkl=∑s=1k1dvs+1−1dvs+2−k+k2=∑s=1k1dvs+1dvs+2−k2.
Replacedvs with minimum degree δ. It maximizes the term ∑s=1k1/dvs+1dvs+2, which implies(9)=∑s=1k1δ+1δ+2−k2=kδ+1δ+2−k2=k2−δ+1δ+2δ+1δ+2=k−δ2−3δδ+1δ+2.
It is clear from (9) that IDGkl−IDAGkl≤0. Hence,(10)IDGkl≤IDAGkl.
The transformationB shown in Figure 2 decreases the degree of one vertex and makes the same increase into the degree of fixed selected vertex:(11)IDBGkl=∑s=1n−kl+11dvs+∑s=1k−21dvs+1+1dvk+1dvk−1+2+kl−22+k.
So, from equations (6) and (11), we get(12)IDGkl−IDBGkl=∑s=1k1dvs+1−∑s=1k−21dvs+1−1dvk−1dvk−1+2,to maximize the fraction involved in above expression replace dvs,0≤s≤k with δ, and we get(13)IDGkl−IDBGkl=2δ+1−1δ−1δ+2=−2δ−2δ2−2δδ+1δ+2≤0.
The equation (13) implies(14)IDGkl≤IDBGkl.Figure 2
TransformationB for q=1.


## 2.1.3. TransformationAij

The transformationAij is composition of Ai,0≤i≤l−1 and Bj,0≤j≤k−1 which is shown in Figure 3. Here, Ai,0≤i≤l−1 be the repetition of transformation A and Bj,0≤j≤k−1 be the repetition of transformation B.Figure 3
TransformationAij.For main results related to the transformationAij shown in Figure 3, we need to prove Propositions 1 and 2.Proposition 1.
Letg:N×W⟶Q defined as gη,ζ=1/η+ζ. Then,(1)
gη,ζ+1≥gη,ζ−1+1/2 for ζ≥1(2)
Forα,β≥0,gη,α+1β+1+gη,0≥gη,αβ+1+gη,β+1Proof.
(1) If transformationA applied on pendent path attached with vertex wj of G having degree η+ζ. The degree of vertex wj increased by one with change of vertex having degree 2 to leaf attached to wj. This change has effect on ID in the following way.
Letgη,ζ=1/η+ζ. Then,(15)gη,ζ+1−gη,ζ−1+12=1η+ζ+1−1η+ζ−1−12=12−1η+ζη+ζ−1.
It is clear from basic calculus that1/α≥1/α+β;β≥0. So,(16)=12−1η+ζη+ζ−1≥0,implies gη,ζ+ζ≥gη,ζ−1.
(2) The 2nd part of this preposition is related to the effect of transformationAij shown in Figure 3:(17)gη,α+1β+1+gη,0−gη,αβ+1+gη,β+1=1α+1β+η+1η−1α∗β+η−1β+η+1=α2β3+3α2β2+3α2β+α2+αβ3+2αβ2η+3αβ2+4αβη+3αβ+2aη+αηβ+η+1αβ+1+ηη+b+1≥0.
Thus,gη,α+1β+1+gη,0≥gη,αβ+1+gη,β+1.Proposition 2.
Letfη=1/η+3/2 and gη=1/η+1+2, then for η≥1, gη≥fη.Proof.
(18)gη−fη=1η+1+2−1η+32=1η+1−1η+12=2η−2η+1+ηη+12ηη+1=η−1+η2−12ηη+1≥0.
This fraction is nonnegative for allη≥1 which implies that gη≥fη.Theorem 2.
LetG be the graph of order n having p pendent vertices. Gkl is the graph having k pendent paths attached to the fully connected vertices with maximum degree of a vertex Δ+1. Then, for 0≤i≤l−1 and α≤β,(19)IDAiαGkl≤IDAiβGkl.Proof.
LetGkl be the graph with order n=n+kl, minimum degree δ, and maximum degree Δ+1. Using the fact of Aij over Gkl, we get(20)IDAijGkl=ki+1+kl−i+12+∑r=1k−j+11dvr+i+1+∑s=1n−p−k+j1dvs+1dvr+j+1i+1+p,for 1≤dr,ds≤Δ≤n−1 and 0≤i≤l−1,0≤j≤k−1. Then, for α≤β,(21)IDAiαGkl−IDAiβGkl=∑r=1k−α+11dvr+i+1+∑s=1n−p−k+α1dvs+1dvr+α+1i+1−∑r=1k−β+11dvr+i+1+∑s=1n−p−k+β1dvs+1dvr+β+1i+1=∑r=k−βk−α−11dvr+i+1−∑s=n−p−k+α+1n−p−k+β1dvs+i+1β−αdvr+i+1α+1dvr+i+1β+1.
So, by using Proposition1 and replacing Δ with dvr and δ with dvs, it is clear that Δ minimizes the positive terms and δ maximizes the negative term. After simplification, we get(22)=β−αδ−ΔΔ+i+1β+1Δ+i+1α+1+δ−ΔΔ+i+1i+1−i+12αΔ+Δ+i+1α+1β+1Δ+lα+1Δ+lβ+1δΔ+1.
It is clear that forα≤β, the nominator is a negative number and denominator is positive which implies that(23)IDAiαGkl−IDAiβGkl≤0.
Thus, forβ≥α,(24)IDAiαGkl≤IDAiβGkl.In the following theorem, we determined bonds ofID for graph Gkl under the effect of transformation Aij by using Propositions 1 and 2.Theorem 3.
LetG be the graph of order n having p pendent vertices. Gkl is the graph with maximum degree Δ+1 having order n+kl with k≤n−p of pendent paths of length l. Then, for IDAijGkl;0≤i≤l−1,0≤j≤k−1,(25)Δ+1Δl+1+2pΔ+n−p−1+2Δ2ΔΔ+1≤IDAijGkl.Equality holds forr-regular graph with i=0,j=0, and k=1. And(26)IDAijGkl≤δ+n−plδln−p+n−1+pδ+δn−pl+δδ,equality holds if under consideration graph is r-regular with k=n−p pendent paths of length l and i=l−1,j=k−1.Proof.
LetG be the graph having order n≥3 with 0≤p≤n−1 pendent vertices with minimum degree δ and maximum degree Δ. Gkl is the graph with maximum degree Δ+1 and maximum number of pendent paths k=n−p of length l. Then, by using equation (20),(27)IDAijGkl=ki+1+kl−i+12+∑r=1k−j+11dvr+i+1+∑s=1n−p−k+j1dvs+1dvr+j+1i+1+p,where 1≤dr,ds≤Δ≤n−1, and 0≤i≤l−1,0≤j≤k−1.
The order ofGkl is fixed. So, the increase in pendent paths causes to decrease their lengths l. This fact increases the number of pendent paths and decreases the vertices of degree two. So, Proposition 2 clears that IDAijGkl increases with the increase in k. It is clear from Theorems 1 and 2 and Propositions 1 and 2 that the least value of IDAijGkl was obtained by setting i,j=0, dr=ds=Δ, and k=1:(28)IDA00G1l≥1+1l−12+1−1Δ+1+n−p−1Δ+1Δ+1+p.
After simplification, we get(29)Δ+1Δl+1+2pΔ+n−p−1+2Δ2ΔΔ+1≤IDAijGkl,and equality holds in (28) for r-regular graph with the k=1 pendent path of length l and i=0,j=0.
Now again from (20), setting i=l−1,j=k−1,dr=ds=δ,k=n−p and using Proposition 1 and Theorems 1, 2, we get maximal value of IDAijGkl as(30)IDAl−1k−1Gkl≤n−pl−1+1+n−pl−l−1+12+∑s=1n−n−p+n−p−11δ+∑r=1n−p−n−p−1+11δ+l−1+1+1δ+n−p−1+1l−1+1+p.
After simplification, we get maximal value ofIDAijGkl as(31)IDAijGkl≤δ+n−plδln−p+n−1+pδ+δn−pl+δδ,in which equality holds for r-regular graph with k=n−p pendent paths of length l and i=l−1,j=k−1.
Inequalities (29) and (31) complete the proof.Theorem 4.
LetG be the graph without pendent vertices and Gkl for k>1 be the graph with maximum degree Δ+1. Then, for 0≤i≤l−1,0≤j≤k−1, the lower bond of IDAijGkl is(32)IDAijGkl≥Δ+1Δkl+1+2n−k+2kΔ2ΔΔ+1.Equality holds forr-regular graph with k pendent paths of length l and i = 0, j = 0.Proof.
LetG be the graph of order n without pendent vertices having minimum degree δ and maximum degree Δ. Gkl be the graph with maximum degree Δ+1 and k≥1 be the count of pendent paths of length l. Then, by using (20),(33)IDAijGkl=ki+1+kl−i+12+∑r=1k−j+11dvr+i+1+∑s=1n−k+j1dvs+1dvr+j+1i+1,where 1≤dr,ds≤Δ≤n−1, and 0≤i≤l−1,0≤j≤k−1. Using Propositions 1 and 2 and setting i,j=0,dr=ds=Δ, we get least value of IDAijGkl as IDA00Gkl:(34)IDA00Gkl=k+kl−12+k−1Δ+1+n−kΔ+1Δ+1.
After simplification, we get minimal value as(35)Δ+1Δkl+1+2n−k+2kΔ2ΔΔ+1≤IDAijGkl.
Equality for equation (3) holds for r-regular graph with k pendent paths of length l and i=0,j=0.Theorem 5.
LetG be the Δ-regular graph. IDAijGkl be the graph with k pendent paths of length l. Then, for 0≤i≤l−1,0≤j≤k−1:(36)IDAijGkl=Δ+i+1jΔ+i+12n−k+j+ki+l+12ΔΔ+i+1jk−j+Δk−j−1+ΔΔ+l2ΔΔ+i+1Δ+ji+1.Proof.
LetG be the Δ-regular graph and k be the count of pendent paths of length l. Then, Gkl is the graph with maximum degree Δ+1. Then, for 0≤i≤l−1,0≤j≤k−1, equation (20) takes the form(37)IDAijGkl=ki+1+kl−i+12+∑r=1k−j+11Δ+i+1+∑s=1n−k+j1Δ+1Δ+j+1i+1.
After simplification, we get required result:(38)IDAijGkl=Δ+i+1jΔ+i+12n−k+j+ki+l+12ΔΔ+i+1jk−j+Δk−j−1+ΔΔ+l2ΔΔ+i+1Δ+ji+1.In Corollary1, we determined exact values of ID for unicyclic graphs with k pendent paths of length l under transformation Aij. Figure 4(a) depicts transformed graph AijCn,kl for i=j=1, k=2 with fixed vertex w1 and Figure 4(b) with fixed vertex w2.Figure 4
TransformationAij effect over Gkl=Cn,2l: (a) transformed graph A11Cn,2l with fixed vertex w1; (b) transformed graph A11Cn,2l with fixed vertex w2.
(a)(b)Corollary 1.
LetCn be the unicyclic graph of order n. Cn,kl is the graph with k pendent paths of length l. Then, for 0≤i≤l−1,0≤j≤k−1,(39)IDAjGkl=2+i+1j3+i2n−k+j+ki+l+142+i+1jk−j+2k−j−1+22+l43+i2+ji+1.Proof.
Cn is the unicyclic graph of order n. Cn is 2-regular graph. Then, we get required result by replacing Δ by 2 in Theorem 5:(40)IDAjGkl=2+i+1j3+i2n−k+j+ki+l+142+i+1jk−j+2k−j−1+22+l43+i2+ji+1.


## 3. Conclusions

Topological indices and graph transformations play a significant role in modern chemistry and computer networks. It is an interesting problem to determine the bonds of the topological index for different families of graphs [5, 6, 9, 16]. In this work, we give graph transformations, A,B, and Aij for variable values of i and j over pendent paths attached with the fully connected vertices of graphs and characterized ID for these transformed graphs. At first, we determined the effect of transformations A and B over increase and decrease of ID individually. Then, we established result for Aij for arbitrary values of i and j which provides moving graphs such as animation. We also determined the exact result for Δ-regular graph under transformation effect. Moreover, we computed the exact formula for the family of unicyclic graphs with pendent paths under the action of transformation as an application of proved results.



---

*Source: 6657039-2021-02-28.xml*