# On the Maximum Symmetric Division Deg Index ofk-Cyclic Graphs

Authors: Abeer M. Albalahi; Akbar Ali
Journal: Journal of Mathematics
 (2022)

---

## Abstract

LetG be a graph. Denote by du, the degree of a vertex u of G and represent by vw, the edge of G with the end-vertices v and w. The sum of the quantities du2+dv2du−1dv−1 over all edges uv of G is known as the symmetric division deg (SDD) index of G. A connected graph with n vertices and n−1+k edges is known as a (connected)k-cyclic graph. One of the results proved in this study is that the graph possessing the largest SDD index over the class of all connectedk-cyclic graphs of a fixed order n must have the maximum degree n−1. By utilizing this result, the graphs attaining the largest SDD index over the aforementioned class of graphs are determined for every k=0,1,…,5. Although, the deduced results, for k=0,1,2, are already known, however, they are proved here in a shorter and an alternative way. Also, the deduced results, for k=3,4,5, are new, and they provide answers to two open questions posed in the literature.


---

## Body

## 1. Introduction

Only finite and connected graphs are discussed in this study. The graph-theory concepts used in this paper without defining them here can be found in [1, 2]. A graph invariant I is a mapping on the class of all graphs with the condition that IG1=IG2 whenever the graphs G1 and G2 are isomorphic to each other. In chemical graph theory, graph invariants are usually referred to as topological indices.The present paper is concerned with a topological index devised in [3], under the name “symmetric division deg (SDD) index,” for improving QSAR/QSPR modeling. The SDD index of a graph G is defined as(1)SDDG=∑uv∈EGdu2+dv2dudv,where EG denotes the edge set of G, uv indicates the edge with end-vertices u,v, and dw denotes the degree of an arbitrary vertex w∈VG. In order to check the chemical applicability of the SDD index, Furtula et al. [4] conducted a thorough multidimensional investigation of the SDD index and discovered that it is a practicable and feasible topological index that outperforms a number of other indices of a similar kind. Ali et al. and Sun et al. [5, 6] provide information on certain extremal results concerning the SDD index. The papers [7,15] may be consulted for different bounds on the SDD index.One of the results proved in this paper is that the graph possessing the largest SDD index over the class of allk-cyclic graphs of a fixed order n must have the maximum degree n−1. By utilizing this result, the graphs attaining the largest SDD index over the aforementioned class of graphs are determined for every k∈0,1,…,5. Although, the deduced results, for k=0,1,2, are already known [8, 9], however, they are proved here in a shorter and an alternative way. Also, the deduced results, for k=3,4,5, are new, and (the case k=3 gives a solution to an open problem given in [10]) they provide an answer to a conjecture posed by Palacios [11].


## 2. Main Results

We start this section by defining a graph transformation that is used in proving one of the main results of this paper.Transformation 1: letv and w be two vertices of a graph G such that (i) dv≥dz, for every z∈NGv∪NGw∪w, and (ii) w has at least one neighbor that is not adjacent to v. Take NGw∖NGv:=w1,w2,…,wk. Form a new graph G′ from G by inserting the edges vw1,vw2,…,vwk and dropping the edges ww1,ww2,…,wwk.We also need the following elementary lemma.Lemma 1.
Define(2)Ψx,y=x2+y2xy,where1≤y≤x.
The functionΨ is a strictly increasing in x, but it is strictly decreasing in y.Proof.
Take two numbersx1 and x2 satisfying 1≤y≤x2<x1. Note that y2<x1x2, which gives x1−x2y2<x1−x2x1x2, and thus, Ψx1,y>Ψx2,y. In a similar way, one concludes that Ψx,y1>Ψx,y2 whenever 1≤y1<y2≤x.Proposition 1.
For0≤k≤n−2, the maximum degree of G is n−1 if it is a graph possessing the largest SDD index among all k-cyclic graphs of order n.Proof.
Contrarily, we consider the case when the maximum degree ofG is different from n−1. Choose v∈VG in such a way that dv≥dz, for every z∈VG. Certainly, there exist vv′∈EG so that the set NGv′ contains at least one element, different from v, that is not a neighbor of v. Suppose that NGv′∖NGv:=v1′,v2′,…,vr′. Let G′ be the graph obtained by applying Transformation 1 on G. Take A=NGv∖NGv′ and B=NGv∩NGv′. In what follows, for an arbitrary vertex z∈VG′=VG, by the vertex degree dz, we mean the degree of the vertex z in G:(3)SDDG′−SDDG=∑x∈A,x≠v′Ψdv+r,dx−Ψdv,dx+∑y∈BΨdv+r,dy−Ψdv,dy+∑y∈BΨdv′−r,dy−Ψdv′,dy+∑i=1rΨdv+r,dvi′−Ψdv′,dvi′+Ψdv+r,dv′−r−Ψdv,dv′,where Lemma 1 contains the definition of Ψ. Now, keeping the facts into consideration that dv′>r≥1 and dv≥dv′, one obtains(4)Ψdv+r,dy−Ψdv,dy+Ψdv′−r,dy−Ψdv′,dy=rdydv+dv′r+dv−dv′dvdv′dv+rdv′−r>0,Ψdv+r,dv′−r−Ψdv,dv′=rdv+dv′2dv−dv′+rdvdv′dv+rdv′−r>0.
Note thatdv≥dvi′ and dv≥dx, for every i∈1,2,…,r and x∈A, respectively. Thus, because of the above observations and Lemma 1, Equation (3) yields SDDG′>SDDG; this contradicts the definition of G because G′ is also a k-cyclic graph of order n.
Proposition1 confirms that the graph(s) possessing the largest SDD index among all k-cyclic graphs of order n must be obtained from the star graph Sn by adding k edge(s) in some way. Since there is exactly one k-cyclic graph of order n with the maximum degree n−1 for every n∈3,4,5,… and k∈0,1, the next already known result follows immediately from Proposition 1.Corollary 1 (see [8, 9]).
The graphSn,k uniquely attains the largest SDD index among all k-cyclic graphs of order n for every k∈0,1 and n∈4,5,6,…, where Sn,k is the graph formed by inserting k edge in the star graph Sn.
Note that there are exactly two bicyclic graphs of ordern with the maximum degree n−1 for every n∈5,6,…; one of them, say Bn,1, is formed by adding two adjacent edges in the star graph Sn, and the other one, say Bn,2, is formed by inserting two nonadjacent edges in Sn. Since(5)SDDBn,1=3n3−14n2+35n−123n−1>n3−5n2+12n−4n−1=SDDBn,2,for every n∈5,6,…, the next already known result follows also immediately from Proposition 1.Corollary 2 (see [9]).
The graphBn,1 uniquely achieves the largest SDD index over the family of all bicyclic graphs of order n for every n∈5,6,….
We note that there is only one tricyclic graph, namely,K4, of order 4. For n≥5, one obtains all the possible tricyclic graphs of order n and maximum degree n−1 from Figure 1. Simple computations yield(6)SDDG1=n3−6n2+16n−5n−1,n≥7,SDDG2=3n3−17n2+47n−153n−1,n≥6,SDDG3=3n3−16n2+45n−143n−1,n≥5,SDDG4=4n3−21n2+64n−234n−1,n≥5,SDDG5=n3−5n2+14n−4n−1,n≥4.
We observe thatSDDG5>SDDGi, for i∈1,2,3. However,(7)SDDG5>SDDG4,whenn≥8,=SDDG4,whenn=7,<SDDG4,whenn∈5,6.Therefore, we have another corollary of Proposition1.Figure 1
All possible tricyclic graphs of ordern and maximum degree n−1.Corollary 3.
The graphG5, shown in Figure 1, attains uniquely the largest SDD index over the family of all tricyclic graphs of order n, for every n∈8,9,….
We remark here that Corollary3 gives a solution to an open problem posed in [10]. Next, we discuss the tetracyclic graphs. For n≥5, Figure 2 contains all the possible tetracyclic graphs of order n and maximum degree n−1. After elementary computations, we have(8)SDDH1=n3−7n2+20n−6n−1,n≥9,SDDH2=3n3−19n2+58n−183n−1,n≥7,SDDH3=3n3−18n2+55n−163n−1,n≥6,SDDH4=5n3−29n2+106n−425n−1,n≥6,SDDH5=12n3−67n2+214n−6312n−1,n≥5,SDDH6=n3−6n2+18n−5n−1,n≥6,SDDH7=12n3−71n2+229n−7412n−1,n≥6,SDDH8=3n3−17n2+52n−143n−1,n≥5,SDDH9=4n3−25n2+80n−274n−1,n≥7,SDDH10=3n−1n2−6n+173n−1,n≥7,SDDH11=3n3−20n2+59n−183n−1,n≥8.
We observe thatSDDH5>SDDHi, for i∈1,2,…,11∖4, and(9)SDDH5>SDDH4,whenn≥15,<SDDH4,when6≤n≤14.Thus, the next result yet is another consequence of Proposition1.Figure 2
All possible tetracyclic graphs of ordern and maximum degree n−1.Corollary 4.
The graphH4 (H5, respectively) pictured in Figure 2, attains uniquely the largest SDD index over the family of all tetracyclic graphs of order n, for every n∈6,7,…,14 (for every n∈15,16,…, respectively).
Finally, we discuss the pentacyclic graphs. We note that there is only one pentacyclic graph of order 5, namely,G17 depicted in Figure 2. For n≥6, Figure 3 contains all the possible pentacyclic graphs of order n and maximum degree n−1. After elementary computations, we have(10)SDDG1=n3−8n2+24n−7n−1,n≥11,SDDG2=12n3−83n2+284n−9312n−1,n≥8,SDDG3=12n3−79n2+266n−7912n−1,n≥7,SDDG4=3n3−19n2+82n−363n−1,n≥7,SDDG5=15n3−92n2+339n−11215n−1,n≥6,SDDG6=3n3−22n2+69n−203n−1,n≥9,SDDG7=12n3−75n2+251n−6812n−1,n≥6,SDDG8=15n3−97n2+361n−12915n−1,n≥7,SDDG9=12n3−75n2+254n−7112n−1,n≥6,SDDG10=5n3−34n2+126n−475n−1,n≥8,SDDG11=12n3−83n2+277n−8612n−1,n≥8,SDDG12=3n3−23n2+71n−213n−1,n≥10,SDDG13=12n3−79n2+262n−7512n−1,n≥7,SDDG14=3n3−21n2+68n−203n−1,n≥8,SDDG15=3n3−20n2+65n−183n−1,n≥7,SDDG16=4n3−29n2+96n−314n−1,n≥9,SDDG17=6n3−35n2+120n−316n−1,n≥5,SDDG18=3n−1n2−7n+213n−1,n≥9,SDDG19=6n3−37n2+129n−386n−1,n≥6,SDDG20=2n3−13n2+46n−152n−1,n≥7,SDDG21=3n3−20n2+64n−173n−1,n≥7,SDDG22=12n3−79n2+269n−8212n−1,n≥7,SDDG23=3n3−19n2+62n−163n−1,n≥6,SDDG24=n3−7n2+22n−6n−1,n≥8,SDDG25=3n3−20n2+65n−183n−1,n≥7,SDDG26=3n3−21n2+67n−193n−1,n≥8.
We observe thatSDDG17>SDDGi, for i∈1,2,…,26∖4,5. Also, it holds that(11)SDDG17>maxSDDG4,SDDG5,for n≥14. Moreover, SDDG4>maxSDDG5,SDDG17, for 7≤n≤13, and SDDG5>SDDG17, for n=6 (the graph G4 does not exist when n=6). Thus, by keeping in mind these observations and using Proposition 1, one gets the next result.Figure 3
All possible pentacyclic graphs of ordern and maximum degree n−1.Corollary 5.
The graphG4 (G17, respectively) given in Figure 3, attains uniquely the largest SDD index over the family of all pentacyclic graphs of order n for every n∈7,…,13 (for every n∈14,16,…, respectively).


## 3. Concluding Remarks

In this study, we have proved that the graph possessing the largest SDD index over the class of allk-cyclic graphs of a fixed order n must have the maximum degree n−1. By utilizing this result, we have determined the graphs possessing the maximum SDD index over the aforementioned class of graphs for 0≤k≤5. Although, the obtained results, for k=0,1,2, are already known [8, 9], however, they are proved here in a shorter and an alternative way. Also, the obtained results, for k=3,4,5, are new, and (the case k=3 gives a solution to an open problem given in [10]) they provide an answer to the following conjecture posed by Palacios [11].Conjecture 1.
For3≤k≤6 and sufficiently large n, among all k-cyclic graphs of a fixed order n, the greatest values of the SDD index and the graph invariant IG=∑v∈VGdv−1are achieved by the same graph G.
Here, we remark that the graph invariantIG=∑v∈VGdv−1 is a special case of the zeroth-order general Randić index ∑v∈VGdvα (for example, see [12]), where α is a real number distinct from 1 and 0. From Corollaries 3–5, and from the results obtained in [13, 14] involving the maximum value of graph invariant I, we deduce that Conjecture 1 is true for (i) k=3 and n≥8, (ii) k=4 and n≥15, and (iii) k=5 and n≥14. It is natural to expect that Conjecture 1 holds also not only for k=6 but also for k≥7; however, the proof of this expected result is left here is an open task.



---

*Source: 7783128-2022-08-27.xml*