# Some Bond Incident Degree Indices of Cactus Graphs

Authors: Akbar Ali; Akhlaq Ahmad Bhatti; Naveed Iqbal; Tariq Alraqad; Jaya Percival Mazorodze; Hicham Saber; Abdulaziz M. Alanazi
Journal: Journal of Mathematics
 (2022)

---

## Abstract

A connected graph in which no edge lies on more than one cycle is called a cactus graph (also known as Husimi tree). A bond incident degree (BID) index of a graphG is defined as ∑uv∈EGfdGu,dGv, where dGw denotes the degree of a vertex w of G, EG is the edge set of G, and f is a real-valued symmetric function. This study involves extremal results of cactus graphs concerning the following type of the BID indices: IfiG=∑uv∈EGfidGu/dGu+fidGv/dGv, where i∈1,2, f1 is a strictly convex function, and f2 is a strictly concave function. More precisely, graphs attaining the minimum and maximum Ifi values are studied in the class of all cactus graphs with a given number of vertices and cycles. The obtained results cover several well-known indices including the general zeroth-order Randić index, multiplicative first and second Zagreb indices, and variable sum exdeg index.


---

## Body

## 1. Introduction

All the graphs considered in this study are connected. The notation and terminology that are used in this study but not defined here can be found in some standard graph-theoretical books [6, 7].Graph invariants of the following form are known as the bond incident degree (BID) indices [5]:(1)BIDG=∑uv∈EGfdGu,dGv,where dGw denotes the degree of a vertex w∈VG of the graph G, EG is the edge set of G, and f is a real-valued symmetric function. In this study, we are concerned with the following type [2] of the BID indices:(2)IfiG=∑uv∈EGfidGudGu+fidGvdGv=∑v∈VGfidGvwhere i∈1,2, f1 is a strictly convex function, and f2 is a strictly concave function.A connected graph in which no edge lies on more than one cycle is called a cactus graph (also known as Husimi tree [9]). In the present study, we study the graphs attaining the minimum and maximum Ifi values from the class of all cactus graphs with a given number of vertices and cycles. Our main results cover the general zeroth-order Randić index 0Rα [3], variable sum exdeg index SEIa [13], multiplicative first Zagreb index Π1 [8], multiplicative second Zagreb index Π2 [1, 8, 10], and sum lordeg index SL [12, 14], where the aforementioned indices for a graph G are defined as follows:(3)0RαG=∑v∈VGdGvα,SEIaG=∑v∈VGdGvadGv,Π1G=∏v∈VGdGv2,Π2G=∏uv∈EGdGudGv=∏v∈VGdGvdGv,SLG=∑v∈VGdGvlndGv=∑v∈VG;dGv≥2dGvlndGv.A graph in which every vertex has degree less than 5 is known as a chemical graph.Although we cannot apply our main result on the Lanzhou index [15] for finding the extremal graphs from the class of all cactus graphs, we still are able to utilize one of our main results for finding the graphs having the minimum Lanzhou index among all chemical cactus graphs, where the Lanzhou index for a graph G is defined as(4)LzG=∑v∈VGn−dGv−1dGv2.We end this section with the remark that the Lanzhou index is same [11] as the graph invariant 0R3.


## 2. Main Results

By ann-vertex graph, we mean a graph of order n. In a graph, a set of pairwise nonadjacent edges is called a matching. The elements of a matching are known as independent edges.Theorem 1.
The graph formed by addingr-independent edges in the n-vertex star Sn (Figure 1) uniquely attains the maximum If1 value and minimum If2 value in the class of all n-vertex cactus graphs having r cycles, where n and r are the fixed integers satisfying the inequalities n≥2r+1, n≥4, and r≥0.Figure 1
The extremal graph mentioned in Theorem1.Proof.
We prove the result for the graph invariantIf1. The result regarding the other invariant can be proved in a fully analogous way. Let G be a graph having the maximum If1 value in the given class of graphs. It is enough to show that G has the maximum degree n−1. Contrarily, we assume that that the maximum degree of G is at most n−2. Let v∈VG be a vertex of maximum degree. Then, there exists at least one neighbor, say w of v which has at least one neighbor not adjacent to v. Let w1,w2,…,wk be those neighbors of w that are not adjacent to v. If G′ is the graph formed by adding the edges w1v,w2v,…,wkv in G and removing the edges w1w,w2w,…,wkw from G (Figure 2), then we have(5)If1G−If1G′=f1dGv−f1dGv+k+f1dGw−f1dGw−k.
Note that the cactus graphsG and G′ have the same number of cycles as well as order. By using Lagrange’s mean value theorem, we conclude that there exist real numbers a1 and a2, such that(6)a1∈dGw−k,dGw,a2∈dGv,dGv+k,If1G−If1G′=kf1′a1−f1′a2.
The factdGw≤dGv implies that a1<a2, which further implies that the right hand side of equation (6) is negative because f1 is a strictly convex function. Thus, one has If1G−If1G′<0, a contradiction to the maximality of If1G.Figure 2
The graph transformation used in the proof of Theorem1. The white vertices and doted edges may or may not exist provided that every edge lies on at most one cycle.Corollary 1.
In the class of alln-vertex cactus graphs having r cycles, the graph formed by adding r independent edges in the n-vertex star Sn uniquely attains the maximum general zeroth-order Randić index 0Rα for α>1 or α<0, maximum variable sum exdeg index SEIa for a>1, maximum multiplicative second Zagreb index Π2, maximum sum lordeg index SL, minimum general zeroth-order Randić index 0Rα for 0<α<1, and minimum multiplicative first Zagreb index Π1, where n and r are the fixed integers satisfying the inequalities n≥2r+1, n≥4, and r≥0.Proof.
We observe that a graphG attains its maximum Π2 value or minimum Π1 value in a class of graphs if and only if G attains its maximum lnΠ2 value or minimum lnΠ1 value, respectively, in the considered class of graphs. We define ϕ1x=xax with a>1 and x≥1; ϕ2x=xα with x≥1 and α>1 or α<0; ϕ3x=xlnx with x≥1; ϕ4x=xlnx with x≥2; ϕ5x=2lnx with x≥1; and ϕ6x=xα with x≥1 and 0<α<1. It can be easily verified that for each i∈1,2,3,4, ϕi is strictly convex and for each j∈5,6, ϕj is strictly concave. Thus, the required conclusion follows from Theorem 1.
A graph of ordern and size m is called an n,m-graph.Lemma 2 (see [4]).
IfG attains the minimum If1 value or maximum If2 value among all connected n,m-graphs and v∈VG, then the minimum degree of G is at least 2, where n and m are the fixed integers satisfying the conditions 3n≥2m, n≥4, and m≥n.The next result is a direct consequence of Lemma2.Corollary 3.
IfG is a graph attaining the minimum If1 value or maximum If2 value in the class of all n-vertex cactus graphs having r cycles, then the minimum degree of G is 2, where n and r are the fixed integers satisfying the inequalities n≥2r+1, n≥6, and r≥2.Denote byNGv the set of neighbors of a vertex v∈VG of a graph G.Theorem 2.
IfG is a graph attaining the minimum If1 value or maximum If2 value in the class of all n-vertex cactus graphs having r cycles and v∈VG, then the minimum degree of G is 2 and(7)dGv≤4,ifvliesonsomecycle,3,otherwise,where n and r are the fixed integers satisfying the inequalities n≥2r+1, n≥6, and r≥2.Proof.
We prove the result for the graph invariantIf1. The result regarding the other invariant can be proved in a fully analogous way. Let G be a graph having the minimum If1 value in the given class of graphs.
From Corollary3, it follows that the minimum degree of G is 2. Next, we prove that(8)dGv≤4,ifvliesonsomecycle,3,otherwise,
First, assume thatv lies one some cycle C of G. Suppose to the contrary that dGv≥5. Let NGv\VC:=v1,v2,…,vr, where VC denotes the set of vertices of the cycle C. For i=1,2,…,r, denote by Mi the component of the graph G−v containing the vertex vi. It is claimed that no more than two vertices of NGv∖VC lie on the same component of the graph G−v; if vk, vl, and vm lie on the same component of the graph G−v, then the vertices vk, vl, vm, and v lie on a cycle whose each edge belongs to more than one cycle of G, which contradicts the definition of G.Case 1.
There exists at least onei, such that the component Mi contains a unique vertex of NGv∖VC.
Suppose, without loss of generality, that the componentM1 contains none of v2,v3,…,vr. We note that there exists at least one component Mj with j≥2, such that Mj contains at least one vertex u∈VG satisfying dGu=2. Certainly, both the graphs G and G′≅G−vv1+uv1 have the same number of cycles and vertices. On the other hand, we have(9)If1G−If1G′=f1dGv−f1dGv−1+f1dGu−f1dGu+1=f1dGv−f1dGv−1−f13−f12.
By using Lagrange’s mean value theorem, we conclude that there exist real numbersa1 and a2, such that(10)a1∈2,3,a2∈dGv−1,dGv,If1G−If1G′=f1′a2−f1′a1.
The assumptiondGv≥5 implies that a1<a2, which further implies that the right hand side of equation (2) is positive because f1 is a strictly convex function. Thus, one has If1G−If1G′>0, a contradiction to the minimality of If1G.Case 2.
For eachi∈1,2,…,r, exactly two vertices of the set NGv∖VC lie on the component Mi.
Suppose, without loss of generality, thatM1=M2. It is clear that M1≠Mj for each j∈3,…,r, and there exists at least one component Mj with j≥3, such that Mj contains at least one vertex w∈VG satisfying dGw=2. It is obvious that both the graphs G and G″≅G−vv1,vv2+wv1,wv2 have the same number of cycles and vertices. On the other hand, we have(11)If1G−If1G″=f1dGv−f1dGv−2+f1dGw−f1dGw+2=f1dGv−f1dGv−2−f14−f12.
By using Lagrange’s mean value theorem, we conclude that there exist real numbersa3 and a4, such that(12)a3∈2,4,a4∈dGv−2,dGv,If1G−If1G″=2f1′a4−f1′a3.
We note, for the present case, that the degree ofv is at least 6, which implies that a3<a4, which further implies that the right hand side of (12) is positive because f1 is a strictly convex function. Thus, one has If1G−If1G″>0, a contradiction to the minimality of If1G.
Thus,dGv≤4 when v lies on some cycle of G.
It is still left to prove thatdGv≤3 when v does not belong to any cycle of G. Suppose to the contrary that dGv=r≥4 and that v does not belong to any cycle of G. As before, we take NGv=v1,v2,…,vr, and for i∈1,2,…,r, we denote by Mi the component of the graph G−v containing the vertex vi. We observe that Mi≠Mj whenever i≠j; if the components Mi and Mj are the same for some i≠j, then the path from vi to vj in G−v together with the path vivvj yields a cycle in G containing v, which is a contradiction. We note that there exists at least one component Mj with j≥2, such that Mj contains at least one vertex x∈VG satisfying dGx=2. It is obvious that both the graphs G and G‴≅G−v1v+v1x have the same number of cycles and vertices. On the other hand, we have(13)If1G−If1G″=f1dGv−f1dGv−1+f1dGx−f1dGx+1=f1dGv−f1dGv−1−f13−f12.
By using Lagrange’s mean value theorem, we conclude that there exist real numbersa5 and a6, such that(14)a5∈2,3,a6∈dGv−1,dGv,If1G−If1G″=f1′a6−f1′a5.
The assumptiondGv≥4 implies that a3<a4, which further implies that the right hand side of equation (4) is positive because f1 is a strictly convex function. Thus, one has If1G−If1G″>0, a contradiction to the minimality of If1G. Thus, dGv≤3 when v does not belong to any cycle of G.Corollary 4.
IfG is a graph attaining the minimum general zeroth-order Randić index 0Rα for α>1 or α<0, minimum variable sum exdeg index SEIa for a>1, minimum multiplicative second Zagreb index Π2, minimum sum lordeg index SL, maximum general zeroth-order Randić index 0Rα for 0<α<1, and maximum multiplicative first Zagreb index Π1, in the class of all n-vertex cactus graphs having r cycles and v∈VG, then the minimum degree of G is 2 and(15)dGv≤4,ifvliesonsomecycle,3,otherwise,where n and r are the fixed integers satisfying the inequalities n≥2r+1, n≥6, and r≥2.Proof.
We observe that a graphG attains its minimum Π2 value or maximum Π1 value in a class of graphs if and only if G attains its minimum lnΠ2 value or maximum lnΠ1 value, respectively, in the considered class of graphs. We define ϕ1x=xax with a>1 and x≥1; ϕ2x=xα with x≥1 and α>1 or α<0; ϕ3x=xlnx with x≥1; ϕ4x=xlnx with x≥2; ϕ5x=2lnx with x≥1; and ϕ6x=xα with x≥1 and 0<α<1. It can be easily verified that for each i∈1,2,3,4, ϕi is strictly convex, and for each j∈5,6, ϕj is strictly concave. Thus, the required conclusion follows from Theorem 2.
We observe that the functionψx=n−1−xx2 is strictly convex for x<n−1/3. Thus, we have the next corollary regarding the Lanzhou index.Corollary 5.
IfG is a graph attaining the minimum Lanzhou index in the class of all n-vertex chemical cactus graphs having r cycles and v∈VG, then the minimum degree of G is 2 and(16)dGv≤4,ifvliesonsomecycle,3,otherwise,where n and r are the fixed integers satisfying the inequalities n≥2r+1, n≥6, and r≥2.



---

*Source: 8325139-2022-01-21.xml*