# Some Vertex/Edge-Degree-Based Topological Indices ofr-Apex Trees

Authors: Akbar Ali; Waqas Iqbal; Zahid Raza; Ekram E. Ali; Jia-Bao Liu; Farooq Ahmad; Qasim Ali Chaudhry
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In chemical graph theory, graph invariants are usually referred to as topological indices. For a graphG, its vertex-degree-based topological indices of the form BIDG=∑uv∈EGβdu,dv are known as bond incident degree indices, where EG is the edge set of G, dw denotes degree of an arbitrary vertex w of G, and β is a real-valued-symmetric function. Those BID indices for which β can be rewritten as a function of du+dv−2 (that is degree of the edge uv) are known as edge-degree-based BID indices. A connected graph G is said to be r-apex tree if r is the smallest nonnegative integer for which there is a subset R of VG such that R=r and G−R is a tree. In this paper, we address the problem of determining graphs attaining the maximum or minimum value of an arbitrary BID index from the class of all r-apex trees of order n, where r and n are fixed integers satisfying the inequalities n−r≥2 and r≥1.


---

## Body

## 1. Introduction

All the graphs discussed in the present paper are finite. The vertex set and edge set of a graphG are denoted by VG and EG, respectively. Denote by duG (or simply by du if there is no confusion about the graph under consideration) the degree of a vertex u∈VG. Those graph-theoretical notation and terminology that are used in this paper without defining here can be found in some standard graph-theoretical books, such as [1, 2].For a graphG, its graph invariant I is a numerical quantity calculated from G by using any rule in such a way that the equation IG=IG′ holds for every graph G′ isomorphic to G. In chemical graph theory, graph invariants are usually referred to as topological indices [3–10]. A topological index of a graph G that depends on the degrees of the vertices of G is known as a vertex-degree-based topological index; similarly, edge-degree-based topological indices are defined. To the best of the present authors’ knowledge, the Platt index [11, 12] is the oldest vertex-degree-based topological index; for a graph G, its Platt index is defined as(1)PlG=∑uv∈EGdu+dv−2.Sincedu+dv−2 is degree of the edge uv, the Platt index is also an edge-degree-based topological index.In the present paper, we are concerned with the following type of vertex-degree-based topological indices:(2)BIDG=∑uv∈EGβdu,dv,which are known as bond incident degree (BID) indices (see, for example, [13]), where β is a real-valued-symmetric function. Those BID indices for which β can be rewritten as a function of du+dv−2 are known as edge-degree-based BID indices. Note that the Platt index defined in equation (1) is a vertex/edge-degree-based BID index. Other examples of BID indices include the first Zagreb index [14], second Zagreb index [15], general Randić index [16, 17], general zeroth-order Randić index [17, 18], general sum-connectivity index [19], natural logarithm of the multiplicative second Zagreb index [20], variable sum exdeg index [21], sum lordeg index [21], augmented Zagreb index [22], general Platt index [23], and Sombor index [24]. The choices of the function β that correspond to the aforementioned BID indices are specified in Table 1.Table 1
Some of the existing bond incident degree indices.
Functionβdu,dvEquation (2) givesNotationdu+dvFirst Zagreb index [14]M1dudvSecond Zagreb index [15]M2dudvαGeneral Randić index [16,17]Rαduα−1+dvα−1General zeroth–order Randić index [17,18]Rα0du+dvαGeneral sum–connectivity index [19]χαlndudvNatural logarithm of the multiplicative second Zagreb index [20]lnΠ2adu+advVariable sum exdeg index [21]SEIalndu+lndvSum lordeg index [21]SLdudv/du+dv−23Augmented Zagreb index [22]AZIdu+dv−2αGeneral Platt index [23]Plαdu2+dv2Sombor index [24]SOIn order to solve an extremal problem concerning the topological indexR1 (which is same as the second Zagreb index, see Table 1), Bollobás et al. [25] considered following generalization of the general Randić index of a graph G:(3)∑uv∈EGdu+ldv+lα,by taking α as any real number and l as any nonnegative integer. We note that the graph invariant (3)(i)
Remains well-defined ifl is any real number greater than −1(ii)
Gives the reduced second Zagreb index [11] when one takes α=1 and l=−1(iii)
Coincides with the variable connectivity index [26–28] if α=−1/2 and l is any nonnegative real numberThus, in what follows, we assume thatl,α∈A×ℝ∪B×ℝ+ and call the graph invariant (3) as the Bollobás—Erdős—Sarkar index and denote it by BESl,α, where A is the set of all real numbers greater than −1, ℝ is the set of all real numbers, ℝ+ is the set of all positive real numbers, and B=−1. Thus, the Bollobás—Erdős—Sarkar index of a graph G is defined as(4)BESl,αG=∑uv∈EGdu+ldv+lα,with l,α∈A×ℝ∪B×ℝ+. Certainly, the Bollobás —Erdős—Sarkar index is a BID index (here, it needs to be mentioned that the graph invariant BESl,1 was defined in [29] for any real number l).A connected graphG is said to be r-apex tree if r is the smallest nonnegative integer for which there is a subset R of VG such that R=r and G−R is a tree. (Unfortunately, the terminology of apex trees and r-apex trees, being used by many researchers particularly in chemical graph theory, may arise confusion with the terminology of apex graphs and r-apex graphs, respectively. According to Mohar [30], a graph G is an apex graph if it contains a vertex w such that G−w is planar. Also, according to Thilikos and Bodlaender [31], a graph is an r-apex graph if it can be made planar by removing at most r vertices.) The set R is known as r-apex set and its members are known as apex vertices. Every tree is a 0-apex tree. (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.) In this paper, we address the problem of determining graphs attaining the maximum or minimum value of an arbitrary BID index from the class of all r-apex trees of order n, where r and n are fixed integers satisfying the inequalities n−r≥2 and r≥1.


## 2. Main Results

The joinG1+G2 of two graphs G1 and G2 is the graph with the vertex set VG1∪VG2 and the edge set EG1∪EG2∪uv:u∈VG1,v∈VG2. If e=uv is not an edge in a graph G, then G+e denotes the graph formed by adding the edge e in G. The complete graph and the star graph of order n are denoted by Kn and Sn, respectively. To state and prove the first main result, we need the following known result.Lemma 1 (see [32]).
LetI be a topological index.(i)
If for every connected noncomplete graphG, the inequality IG+e>IG holds for every e∉EG; then, the graph attaining the maximum value of the topological index I among all r-apex trees of order n is isomorphic to the join Kr+T, where r and n are fixed integers satisfying the inequalities r≥1 and n−r≥2 and T is a tree of order n−r.(ii)
If for every connected noncomplete graphG, the inequality IG+e<IG holds for every e∉EG; then, the graph attaining the minimum value of the topological index I among all r-apex trees of order n is isomorphic to the join Kr+T, where r and n are fixed integers satisfying the inequalities r≥1 and n−r≥2 and T is a tree of order n−r.For a graphG and a vertex u∈VG, denote by NGu the set of all those vertices of G that are adjacent to u. Now, we state and prove our first main result.Theorem 1.
Letℝ be the set of all real numbers. Let β:ℝ×ℝ⟶ℝ be a real-valued-symmetric function such that(i)
The inequalityβx+s,y−s−βx,y≥0 holds for x≥y>s≥1 and y≥3(ii)
Bothβ and βx are increasing in x, where βx denotes the partial derivative of β with respect to x(iii)
The functionβ satisfies at least one the following additional conditions: β is strictly increasing; βx+s,y−s−βx,y>0
IfBIDG=∑uv∈EGβdu,dv is a bond incident degree index such that, for every connected noncomplete graph H, the inequality BIDH+e>BIDH holds for every e∉EH; then, Kr+Sn−r uniquely attains the maximum BID index among all r-apex trees of order n, where r and n are fixed integers satisfying the inequalities r≥1 and n−r≥2.Proof.
LetG⋆ be a graph attaining the maximum BID index in the given class of graphs. From Lemma 1, it follows that G⋆ is the join of the complete graph Kr and a tree T of order n−r. It remains to prove that T≅Sn−r. Suppose to the contrary that T≇Sn−r. Let v∈VT be a vertex of maximum degree in T. Then, there exist vertices uandu1∈VT such that vuu1 is a path in T. Take NTu=v,u1,u2,…,ut. Let G′ be the graph deduced from G⋆ by deleting the edges u1u,u2u,…,utu and adding the edges u1v,u2v,…,utv. Observe that the graph G′ remains an r-apex tree of order n. In the remaining proof, by the vertex degree ds, we mean degree of the vertex s in the graph G⋆. Now, by using the definition of the BID index and the constraints on the function β, we get(5)BIDG′−BIDG⋆=∑w∈NTv,w≠uβdv+t,dw−βdv,dw+∑z∈VKrβdv+t,dz−βdv,dz+∑z∈VKrβdu−t,dz−βdu,dz+∑i=1tβdv+t,dui−βdu,dui+βdv+t,du−t−βdv,du>rβdv+s,n−1−βdv,n−1+rβdu−s,n−1−βdu,n−1.
Sinceβx is increasing, the right hand side of (5) is nonnegative, which contradicts our assumption that G⋆ attains the maximum BID index among all r-apex trees of order n.
Since every functionβx,y∈x+yα,x+y−2α,x2+y2,ax+ay satisfies all the conditions of Theorem 1, with α≥1 and a>1, the next result is an immediate consequence of Theorem 1.Corollary 1.
Among allr-apex trees of order n, the join Kr+Sn−r uniquely attains the maximum values of the Sombor index, general sum-connectivity index χα, general Platt index Plα, and variable sum exdeg index SEIa, where α≥1, a>1, and r and n are fixed integers satisfying the inequalities r≥1 and n−r≥2.
The extremal result concerning the general sum-connectivity indexχα mentioned in Corollary 1 was proven by using some other way: in [33], for α=1 and r=1; in [34, 35], for α=1 and r≥1; in [36], for α>1 and r≥1. Also, the result concerning SEIa mentioned in Corollary 1 was proven in [37] for r=1 by other means. Moreover, the result concerning the topological index Pl2 mentioned in Corollary 2 was proven by using some other way in [38] for r≥1.
Since the proof of the next result is fully analogous to that of Theorem1, we omit it.Theorem 2.
Letℝ be the set of all real numbers. Let β:ℝ×ℝ⟶ℝ be a real-valued-symmetric function such that(i)
The inequalityβx+s,y−s−βx,y≤0 holds for x≥y>s≥1 and y≥3(ii)
Bothβ and βx are decreasing in x, where βx denotes the partial derivative of β with respect to x(iii)
The functionβ satisfies at least one the following additional conditions: β is strictly decreasing; βx+s,y−s−βx,y≤0
IfBIDG=∑uv∈EGβdu,dv is a bond incident degree index such that, for every connected noncomplete graph H, the inequality BIDH+e<BIDH holds for every e∉EH; then, Kr+Sn−r uniquely attains the minimum BID index among all r-apex trees of order n, where r and n are fixed integers satisfying the inequalities r≥1 and n−r≥2.
Theorems1 and 2 can be improved if one considers the BID indices of the following form:(6)BIDiG=∑uv∈EGβidudu+βidvdv=∑u∈VGβidu,where i∈1,2, β1′ is a strictly increasing function, and β2′ is a strictly decreasing function (where βi′ denotes the derivative of βi).Theorem 3.
Letℝ be the set of all real numbers. For i=1and2, let βi:ℝ⟶ℝ be a real-valued symmetric function. Also, let β1′ be strictly increasing and β2′ be strictly decreasing, where βi′ denotes the derivative of βi. Let BIDiG=∑uv∈EGβidu/du+βidv/dv=∑v∈VGβidv such that, for every connected noncomplete graph H, the inequality(i)
BID1H+e>BID1H holds for every e∉EH; then, Kr+Sn−r uniquely attains the maximum value of the BID1 index among all r-apex trees of order n, where r and n are fixed integers satisfying the inequalities r≥1 and n−r≥2(ii)
BID2H+e<BID2H holds for every e∉EH; then, Kr+Sn−r uniquely attains the minimum value of the BID2 index among all r-apex trees of order n, where r and n are fixed integers satisfying the inequalities r≥1 and n−r≥2Proof.
We prove part (i) of the theorem. Part (ii) can be proved in a fully analogous way. LetG⋆ be a graph attaining the maximum value of the BID1 index in the given class of r-apex trees. From Lemma 1, it follows that G⋆ is the join of the complete graph Kr and a tree T of order n−r. It remains to prove that T≅Sn−r. Suppose to the contrary that T≇Sn−r. Let v∈VT be a vertex of maximum degree in T. Then, there exist vertices uandu1∈VT such that vuu1 is a path in T. Take NTu=v,u1,u2,…,ut. Let G′ be the graph deduced from G⋆ by deleting the edges u1u,u2u,…,utu and adding the edges u1v,u2v,…,utv. Observe that the graph G′ remains an r-apex tree. In the remaining proof, by the vertex degree ds, we mean degree of the vertex s in the graph G⋆. Here, we have(7)BID1G⋆−BID1G′=β1dv−β1dv+t+β1du−β1du−t.
By Lagrange’s mean value theorem, there exist real numbersa1 and a2 such that(8)a1∈du−t,du,a2∈dv,dv+t,and(9)BID1G⋆−BID1G′=tβ1′a1−β1′a2.
The inequalitydu≤dv gives a1<a2, which implies that the right hand side of equation (9) is negative, because β1′ is strictly increasing. Thus, we have BID1G⋆−BID1G′<0, which contradicts our assumption that G⋆ attains the maximum value of the BID1 index among all r-apex trees of order n.
The next result follows directly from the first part of Theorem3.Corollary 2.
Among allr-apex trees of order n, the join Kr+Sn−r uniquely attains the maximum values of the general zeroth-order Randić index Rα0 for α>1, multiplicative second Zagreb index Π2, and sum lordeg index, where r and n are fixed integers satisfying the inequalities r≥1 and n−r≥2.Proof.
It is clear that any graphG has the maximum Π2 value in a given graph class if and only if G has the maximum lnΠ2 value in the considered graph class. Define the functions ϕ1x=xα with x≥1 and α>1, ϕ2x=xlnx with x≥1, and ϕ3x=xlnx with x≥2 (see [39]). Observe that, for every i∈1,2,3, the derivative function ϕi′ of ϕi is strictly increasing. Hence, the desired result now follows from Theorem 3.Remark 1.
The result concerning the general zeroth-order Randić index mentioned in Corollary3 was proven by using some other way: in [40] for α>1 and r=1; in [41] for α=3 and r≥1; in [42] for α>1 and r≥1.
For proving our next result, we need the following known result.Lemma 2 (see [32]).
LetI be a topological index.(i)
If for every connected noncomplete graph, the inequalityIG+e>IG holds for every e∉EG; then, the graph attaining the minimum value of the topological index I among all 1-apex trees of a fixed order is a unicyclic graph, and its unique cycle has a vertex of degree 2.(ii)
If for every connected noncomplete graph, the inequalityIG+e<IG holds for every e∉EG; then, the graph attaining the maximum value of the topological index I among all 1-apex trees of a fixed order is a unicyclic graph, and its unique cycle has a vertex of degree 2.Note that, for the general zeroth-order Randić index0Rα, it holds that, for every connected noncomplete graph G, one has(10)Rα0G+e>0RαG,ifα>0,<0RαG,ifα<0,for every e∉EG. Also, note that the class of all (connected) unicyclic graphs forms a subclass of the class of all 1-apex trees. Moreover, in [43], it was proven that among all unicyclic graphs of a fixed order n≥4, the graph Sn+ formed by adding an edge in the star Sn attains the maximum general zeroth-order Randić index 0Rα for α<0, Sn+ attains the minimum general zeroth-order Randić index 0Rα for 0<α<1, and the cycle graph Cn attains the minimum general zeroth-order Randić index 0Rα for α>1. Thus, keeping in mind these observations and Lemma 5, one gets the next result.Corollary 3.
Among all 1-apex trees of a fixed ordern≥4, the graph Sn+ formed by adding an edge in the star Sn attains the maximum general zeroth-order Randić index 0Rα for α<0, Sn+ attains the minimum general zeroth-order Randić index 0Rα for 0<α<1, and the cycle graph Cn attains the minimum general zeroth-order Randić index 0Rα for α>1.We remark here that Corollary 3 We remark here that Corollary 6was proven in [40] by using some other way.Next, we derive a result about the augmented Zagreb index of 1-apex trees. For this, we need the following lemma first.Lemma 3 (see [44]).
For every fixed integern≥4, the graph formed by adding an edge in the star Sn uniquely attains the minimum AZI in the class of all unicyclic graphs with n vertices, and the minimum value is(11)n−3n−13n−23+24.Since for every connected noncomplete graphG, it holds that AZIG+e>AZIG for every e∈EG (see [44]), and the next result follows from Lemmas 5 and 7.Theorem 4.
For every fixed integern≥6, the graph formed by adding an edge in the star Sn uniquely attains the minimum AZI in the class of all 1-apex trees of order n, and the minimum value is(12)n−3n−13n−23+24.
Theorem4 was proven in [45] by using some other way.
Finally, we determine the unique graph attaining the maximum value ofBESl,1. For this, we need the following two results concerning the Zagreb indices of r-apex trees.Lemma 4 (see [34, 35]).
IfG is an r-apex tree of order n, then it holds that(13)M1G≤r+1n−12+n−r−1r+1,with equality if and only if G≅Sn−r+Kr, where n−r≥2 and r≥1.Lemma 5 (see [34, 35]).
IfG is an r-apex tree of order n, then it holds that (14)M2G≤r+1n−13nr+2n−2r2−5r−22, with equality if and only if G≅Sn−r+Kr, where n−r≥2 and r≥1.From the following identity,(15)BESl,1=M2G+l⋅M1G+l2,Lemmas4 and 5, the next result follows.Theorem 5.
In the class of allr-apex trees of order n, the join Sn−r+Kr uniquely attains the maximum BESl,1-value, where n and r are fixed integers satisfying the inequalities n−r≥2 and r≥1 and l is any nonnegative real number. In other words, if G is an r-apex tree of order n, then it holds that(16)BESl,1G≤r+1rn−1+l2+r+1+ln−1+ln−r−1,with equality if and only if G≅Sn−r+Kr.Theorem5 remains true if one replace the condition “l is any nonnegative real number” with “l is any real number greater than or equal to −1.” To prove this modified statement of Theorem 5, we cannot use identity (15) because of the negative values of l. In what follows, we prove the aforementioned statement (Theorem 6) by using some other way. For this, we need some additional lemmas first.Lemma 6.
Letu1 and u2 be two nonadjacent vertices of a graph G. The inequality BESl,1G+u1u2>BESl,1G holds for every real number l greater than −1. Also, it holds that(17)BES−1,1G+u1u2=BES−1,1G,if one ofu1andu2is isolated and the other haseither no neighbor or pendent neighbors only,>BES−1,1G,otherwise.Proof.
The result immediately follows from the definition ofBESl,1.Lemma 7 (see [46, 47]).
IfT is a tree of order n≥4, then it holds that(18)M1T≤nn−1,with equality if and only if T≅Sn.Lemma 8 (see [48]).
IfT is a tree of order n≥4, then it holds that(19)M2T≤n−12,with equality if and only if T≅Sn.Now, we are able to state and prove our final result.Theorem 6.
In the class of allr-apex trees of order n, the join Sn−r+Kr uniquely attains the maximum BESl,1-value, where n and r are fixed integers satisfying the inequalities n−r≥2 and r≥1 and l is any real number greater than or equal to −1. In other words, if G is an r-apex tree of order n, then it holds that(20)BESl,1G≤r+1n−1+lrn−1+l2+r+1+ln−r−1,with equality if and only if G≅Sn−r+Kr.Proof.
Suppose thatG∗ is a graph attaining the maximum BESl,1-value in the given class of graphs. From Lemmas 1 and 6, it follows that the graph G∗ is isomorphic to the join Kr+T, where T is a tree of order n−r. Let u∈VG∗ be a vertex of degree n−1. Note that the size of the graph Kr+T is(21)rr−12+rn−r+n−r−1=r2n−r−32+n−1.
Thus, the size ofG∗−u is(22)r2n−r−32.
Also, one has(23)BESl,1G∗=duG∗+l∑x∈VG∗−udxG∗+l+∑yz∈EG∗−udyG∗+ldzG∗+l=n+l−1∑x∈VG∗−udxG∗−u+l+1+∑yz∈EG∗−udyG∗−u+l+1dzG∗−u+l+1=n+l−1r2n−r−3+n−1l+1+M2G∗−u+l+1⋅M1G∗−u+r2n−r−3l+122.
We note that the vertexu is an apex vertex and the graph G∗−u is an r−1-apex tree of order n−1. If r=1, then one gets the desired result by using Lemmas 7 and 8 in equation (23). If r≥2, then one gets the desired result by using Lemmas 4 and 5 in equation (23).
The next result about the reduced second Zagreb indexRM2 is a special but notable case of Theorem 6.Corollary 4.
IfG is an r-apex tree of order n, then it holds that(24)RM2G≤r+1n−2rn−22+rn−r−1,with equality if and only if G≅Sn−r+Kr, where n−r≥2 and r≥1.



---

*Source: 4349074-2021-10-21.xml*