# Some Bond Incident Degree Indices of (Molecular) Graphs with Fixed Order and Number of Cut Vertices

Authors: Abeer M. Albalahi; Akbar Ali; Tayyba Zafar; Wael W. Mohammed
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

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. The choice fdGu,dGv=adGu+adGv in the aforementioned formula gives the variable sum exdeg index SEIa, where a≠1 is any positive real number. A cut vertex of a graph G is a vertex whose removal results in a graph with more components than G has. A graph of maximum degree at most 4 is known as a molecular graph. Denote by Vn,k the class of all n-vertex graphs with k≥1 cut vertices and containing at least one cycle. Recently, Du and Sun [AIMS Mathematics, vol. 6, pp. 607–622, 2021] characterized the graphs having the maximum value of SEIa from the set Vnk for a>1. In the present paper, we not only characterize the graphs with the minimum value of SEIa from the set Vnk for a>1, but we also solve a more general problem concerning a special type of BID indices. As the obtained extremal graphs are molecular graphs, they remain extremal if one considers the class of all n-vertex molecular graphs with k≥1 cut vertices and containing at least one cycle.


---

## Body

## 1. Introduction

Graph invariants of the following form are known as the bond incident degree (BID) indices [1–4]:(1)BIDG=∑uv∈EGfdGu,dGv,where dGw denotes the degree of a vertex w of the graph G, EG is the edge set of G, and f is a real-valued symmetric function. In this paper, we are concerned with the following type [5] of the BID indices:(2)IfiG=∑uv∈EGfidGudGu+fidGvdGv=∑v∈VGfidGv,where i∈1,2, f1 is a strictly increasing and strictly convex function, while f2 is a strictly decreasing and strictly concave function.Ifa≠1 is a positive real number, then the variable sum exdeg index SEIa of a graph G can be defined as(3)SEIaG=∑v∈VGdGvadGv.The graph invariantSEIa was introduced in 2011 by Vukičević [6] for predicting the octanol-water partition coefficient of chemical compounds. For detail about the mathematical results on the variable sum exdeg index, we refer the interested readers to references [7–12].A cut vertex of a graphG is a vertex whose removal results in a graph with more components than G has. An n-vertex graph is a graph of order n. Let Vnk be the set of all n-vertex graphs with k≥1 cut vertices and containing at least one cycle.Nowadays, finding graphs with maximum or minimum values of some graph quantity from a given class of graphs is one of the popular problems in chemical graph theory. Recently, Du and Sun [13] characterized the graphs with the maximum variable sum exdeg index SEIa from the set Vnk when a>1. The main motivation of the present paper comes from [13]. In this paper, we not only characterize the graphs with the minimum variable sum exdeg index SEIa from the set Vnk for a>1, but also we solve a more general problem concerning the BID indices If1 and If2. By using the obtained general result, we also characterize the graphs with the minimum general zeroth-order Randić index R0α (see [14]) when α>1, minimum multiplicative second Zagreb index Π2 (see [15]), and minimum sum lordeg index SL (see [16–18]) from the class Vnk, where(4)R0αG=∑v∈VGdGvα,(5)Π2G=∏v∈VGdGvdGv,(6)SLG=∑v∈VGdGvlndGv=∑v∈VG;dGv≥2dGvlndGv.We note that equation (5) gives(7)lnΠ2G=∑v∈VGdGvlndGv,which is minimum in a given class of graphs if and only if Π2G is minimum in the considered class of graphs.A graph of maximum degree at most 4 is known as a molecular graph. As the obtained extremal graphs are molecular graphs, they remain extremal if one considers the class of alln-vertex molecular graphs with k≥1 cut vertices and containing at least one cycle.All the graphs considered in this paper are connected. The notation and terminology that are used in this paper but not defined here can be found in some standard graph-theoretical books, like [19, 20].


## 2. Lemmas

A cut vertex ofG is a vertex whose removal increases the number of components of G. Denote by Vnk the class of all connected n-vertex graphs with k cut vertices and containing at least one cycle. In this section, in order to obtain the main result, we establish some preliminary lemmas.Lemma 1.
Ifv1 and v2 are adjacent vertices of a graph G, then it holds that(8)If1G−v1v2<If1G,If2G−v1v2>If2G.Proof.
The proof follows directly from the definitions ofIf1 and If2.A cactus graph is a connected graph in which every pair of cycles has at most one vertex in common.Lemma 2.
IfG is a graph having the minimum (maximum) If1(If2, respectively) value among all graphs of the class Vnk, then G is a cactus graph.Proof.
IfG is not a cactus graph, then there exists at least one edge, say uv∈EG, lying on at least two cycles of G. Thus, the number of cut vertices of G−uv and G is the same, that is, G−uv∈Vnk. But Lemma 1 forces that If1G−uv<If1G and If2G−uv>If2G, which is a contradiction.A nontrivial connected graph containing no cut vertex is known as a nonseparable graph. A nonseparable subgraphB of a connected graph is said to be maximal nonseparable subgraph if B is not a proper subgraph of any other nonseparable subgraph of G. A block in a graph G is defined as a maximal nonseparable subgraph of G. The next corollary follows directly from Lemma 2.Corollary 1.
IfG is a graph having the minimum (maximum) If1(If2, respectively) value among all graphs of the class Vnk, then every block of G is either a cycle or K2 (complete graph of order 2).Lemma 3.
IfG is a graph having the minimum (maximum) If1(If2, respectively) value among all graphs of the class Vnk, then G contains exactly one cycle.Proof.
Suppose to the contrary thatG has at least two cycles, say C and C′. By Lemma 2, G is a cactus graph.
We claim that each of the cyclesC and C′ has length at least 4. Contrarily, suppose that at least one of C and C′ has length 3. Without loss of generality, we assume that C has length 3. Then, there exists at least one edge, say xy, on C such that G−xy∈Vnk (if all the three vertices of C are cut vertices, then xy may be chosen arbitrarily; if exactly two vertices of C are cut vertices, then xy may be chosen in such a way that exactly one of x and y is a cut vertex; if exactly one vertex of C is a cut vertex, then xy may be chosen in such a way that neither of x and y is a cut vertex), and hence, by using Lemma 1, we have If1G−uv<If1G and If2G−uv>If2G, a contradiction.
Letw∈VG be a cut vertex lying on C such that w1 and w2 are the neighbors of w that also lie on C. Let u (different from w) be a neighbor of w1. Let xy∈EG be an edge lying on the cycle C′. Let us take G′=G−w1u,w2w,xy+ux,w2y. Then, we have(9)IfiG−IfiG′=fidGw−fidGw−1+fidGw1−fidGw1−1.
Sincef1 is strictly increasing and f2 is strictly decreasing, from equation (9), it follows that(10)IfiG−IfiG′>0,ifi=1,<0,ifi=2,which is a contradiction.A graph containing exactly one cycle is known as a unicyclic graph. Since the cycle graphCn of order n has no cut vertex and it is the only unicyclic graph of minimum degree at least 2, the next result is an immediate consequence of Lemma 3.Corollary 2.
IfG is a graph having the minimum (maximum) If1(, respectively) value among all graphs of the class Vnk, then the minimum degree of G is one.Lemma 4.
LetG be a unicyclic graph. Let v∈VG be a pendent vertex having a neighbor w of degree at least 3 such that w remains a cut vertex in G−v. Let xy∈EG be an edge lying on the unique cycle of G. It holds that(11)IfiG−IfiG−wv,xy+xv,vy>0,ifi=1,<0,ifi=2.Proof.
We have(12)IfiG−IfiG−wv,xy+xv,vy=fidGw−fidGw−1+fidGv−fidGv+1=fidGw−fidGw−1−fi2−fi1.
Due to Lagrange’s mean value theorem, there exist numbersθ1 and θ2 such that(13)θ1∈dGw−1,dGw,θ2∈1,2,(14)IfiG−IfiG−wv,xy+xv,vy=fi′θ1−fi′θ2.
We recall thatdGw≥3, which implies that θ1>θ2, and hence, the right-hand side of equation (14) is positive for i=1 and negative for i=2 because f1 is strictly convex and f2 is strictly concave.A pathP:v1v2…vr in a graph G is called a pendent path if one of the two vertices v1, vr, is pendent and the other has degree greater than 2, and every other vertex (if exists) of P has degree 2. If P:v1v2…vr is a pendent path in which v1 has degree greater than 2, then v1 is known as the branching vertex. Two pendent paths are said to be adjacent if they have the same branching vertex.Lemma 5.
LetG be a unicyclic graph. Let P:wv1v2…vr and P′:wu1u2…uq be two adjacent pendent paths in G, where r,q≥2. Let xy∈EG be an edge lying on the unique cycle of G. It holds that(15)IfiG−IfiG−v1v2,v1w,xy+v1x,v1y,uqv2>0,ifi=1,<0,ifi=2.Proof.
For simplicity, we takeG′=G−v1v2,v1w,xy+v1x,v1y,uqv2. Now, we have(16)IfiG−IfiG′=fidGw−fidGw−1−fi2−fi1,which is positive for i=1 and negative for i=2 (see the proof of Lemma 4).Lemma 6.
LetG be a unicyclic graph. Let P:wv1v2…vr and P′:w′u1u2…uq be two nonadjacent pendent paths in G, where each of the vertices w and w′ has degree greater than 2. It holds that(17)IfiG−IfiG−wv1+v1uq>0,ifi=1,<0,ifi=2.Proof.
The proof is analogous to that of Lemma4 and hence omitted.


## 3. Main Result

In this section, we state and prove the lower bound onIf1 and upper bound on If2 for the graphs belonging to Vnk. The graphs attaining these bounds are characterized as well.LetCn,k be the graph deduced from the cycle graph Cn−k of order n−k and path graph Pk+1 of order k+1 by identifying a vertex of Cn−k with an end-vertex of Pk+1 (see Figure 1).Figure 1
The graphCn,k.Theorem 1.
IfG∈Vnk, then(18)Ifi≥n−2f12+f13+f11,ifi=1,≤n−2f22+f23+f21,ifi=2,where the equality sign in any of these inequalities holds if and only if G is isomorphic to Cn,k (see Figure 1).Proof.
Simple calculations yield(19)IfiCn,k=n−2fi2+fi3+fi1.
We prove the inequality involvingIf1 and the other inequality can be proven in a fully analogous way. Let Gmin be a graph having the minimum If1 value among all graphs of the class Vnk. From Lemma 3, it follows that Gmin contains exactly one cycle. Lemma 4 guaranties that Gmin does not contain a pendent vertex having a neighbor w of degree greater than 2 such that w remains a cut vertex in Gmin−v. Also, Lemma 5 forces that Gmin does not contain any pair of adjacent pendent paths of lengths at least 2. Finally, from Lemma 6, it follows that Gmin cannot have nonadjacent pendent paths. Thus, Gmin is isomorphic to the graph Cn,k.Corollary 3.
Among all the members ofVnk, Cn,k is the unique graph attaining the minimum variable sum exdeg index SEIa for a>1, minimum general zeroth-order Randić index R0α for α>1, minimum multiplicative second Zagreb index Π2, and minimum sum lordeg index SL.Proof.
We note that a graphG has the minimum Π2 value in Vnk if and only if G has the minimum lnΠ2 value in Vnk. Define g1x=xax with a>1 and x≥1; g2x=xα with α>1 and x≥1; g3x=xlnx with x≥1; and g4x=xlnx with x≥2. For every i∈1,2,3,4, the function gi is strictly increasing and strictly convex, and hence, from Theorem 1, the desired result follows.Remark 1.
As the extremal graphCn,k mentioned in Theorem 1 and Corollary 3 is a molecular graph, Cn,k remains extremal if one considers the class of all n-vertex molecular graphs with k≥1 cut vertices and containing at least one cycle instead of Vnk in Theorem 1 and Corollary 3.



---

*Source: 9970254-2021-11-25.xml*