# On the Maximum Sombor Index of Unicyclic Graphs with a Fixed Girth

Authors: B. Senthilkumar; Y. B. Venkatakrishnan; S. Balachandran; Akbar Ali; Tariq A. Alraqad; Amjad E. Hamza
Journal: Journal of Mathematics
 (2022)

---

## Abstract

LetG be a graph having the set of edges EG. Represent by dGu the degree of a vertex u of G. The Sombor (SO) index of G is defined as SOG=∑uv∈EGdGu2+dGv2. The length of a shortest cycle in a graph G is known as the girth of G. A connected graph with the same order and size is usually referred to as a (connected) unicyclic graph. This paper reports the characterization of the graphs possessing the first-two maximum values of the SO index in the class of all (connected) unicyclic graphs with a fixed girth and order.


---

## Body

## 1. Introduction

In this paper, we are concerned with only connected and finite graphs. Thus, throughout this study, the term “graph” means a connected and finite graph. The graph-theoretical terminology utilized in this work without giving their definitions may be found in the books [1–3].For a graphG, represent by EG and VG the sets of edges and vertices, respectively. For a vertex u∈VG, the set NGu consists of all those vertices of G that are adjacent with u. The degree of a vertex u∈VG is represented by dGu, which is equal to the number of elements of the set NGu. If dGu=1, then u is called a pendent vertex, and if dGu≥3, then u is called a branching vertex. Denote by G−w the graph deduced from G by removing the vertex w∈VG as well as its incident edges. The length of a shortest cycle in a graph G is known as the girth of G. A connected graph with the same order and size is usually referred to as a unicyclic graph. In other words, a connected cyclic graph having cyclomatic number one is known as a unicyclic graph [4].The Sombor (SO) index for a graphG is defined [5] as(1)SOG=∑uv∈EGdGu2+dGv2.The SO index, although proposed recently [5], has received a lot of attention from academics and led to numerous articles; for instance, see the surveys [6, 7] and associated references are given therein. Possible chemical applications of the SO index may be found in the papers [8, 9].In the present article, we are concerned with the solution to an extremal problem involving the SO index for unicyclic graphs with a fixed girth and order. The SO index of unicyclic graphs has been studied in several papers. The graphs possessing the least and largest values of the SO index among all unicyclic graphs with a fixed order were found independently in [10, 11]. Liu [12] (respectively, Alidadi et al. [13]) reported the graphs attained the highest value (respectively, least value) of the SO index among all unicyclic graphs with a fixed diameter and order. The graphs attaining the minimum (respectively, maximum) SO index over the class of all unicyclic graphs with a fixed maximum degree (respectively, matching number) and order were characterized in [14] (respectively, in [15]). In this paper, we give the characterization of the graphs possessing the first-two maximum values of the SO index in the class of all unicyclic graphs with a fixed girth and order.


## 2. Main Results

We start this section with an elementary lemma.Lemma 1.
Fora>b≥1 and x≥1, the function f defined by(2)fx=a2+x2−b2+x2,is strictly decreasing.Next, we provide a lemma that is crucial for proving our first main result.Lemma 2.
LetG be a connected graph of order at least 4. Let u and v be adjacent vertices of degrees at least 2 such that they do not have any neighbor in common. Let H be the graph deduced from G by dropping all the edges, except uv, incident with v and inserting the edges ux for all x∈NGv∖u. Then, SOG<SOH.Proof.
IfNGv=u,v1,v2,…,vs, where s≥1, then(3)SOH−SOG=∑w∈NGu∖vdGu+s2+dGw2−dGu2+dGw2+∑i=1sdGu+s2+dGvi2−s+12+dGvi2+dGu+s2+1−dGu2+s+12>dGu+s2+1−dGu2+s+12>0,as desired.
The next result gives the characterization of the graphs possessing the first maximum value of the SO index in the class of all unicyclic graphs with a fixed girth and order.Theorem 1.
IfG is a unicyclic graph with order n and girth k, then(4)SOG≤n−kn−k+22+1+2n−k+22+4+k−28,with equality if and only if G=Ck,n−k, where Ck,n−k is the graph formed by attaching n−k pendent vertex/vertices to exactly one vertex of the cycle graph Ck of order k.Proof.
In [11], it was proved that C3,n−3 is the unique graph having the maximum Sombor index among all unicyclic graphs of order n; thus, our theorem follows from this result when k=3. In the rest of the proof, we assume that 4≤k≤n. Also, suppose that SOG is as large as possible. By Lemma 2, every vertex that lies on the cycle of G has exactly two nonpendent neighbors. Note that n can be written in terms of k; that is, n=k,k+1,k+2,…. Now, we apply induction on n. The result trivially holds for n∈k,k+1, because there is only one graph in either of these two cases. Thence, the induction starts. Let w∈VG be a pendent vertex having the neighbor v. Take NGv=w,v1,v2,…,vq−1 with dGvi=qi for each i∈1,2,…,q−1 and dGv=q≥3. Note that n−k+2≥q and that exactly two members of NGv are nonpendent. Observe that the graph G−w has order n−1 and girth k.
By Lemma1, one has(5)SOG=SOG−w+∑i=1q−1q2+qi2−q−12+qi2+q2+1≤SOG−w+q2+1+2q2+22−q−12+22+q−3q2+1−q−12+1,(6)=SOG−w+q−2q2+1+2q2+4−q−3q−12+1−2q−12+4,where the equality sign in (5) holds if and only if each of the two nonpendent neighbors of v has degree 2. Note that the function ψ defined by(7)ψx=x−2x2+1+2x2+4−x−3x−12+1−2x−12+4,is strictly increasing for x≥3 because its derivative(8)ψ′x=x2+1+x−2xx2+1+2xx2+4−x−3x−1x−12+1−2x−1x−12+4−x−12+1,is positive for x≥3 as the inequalities(9)x−2xx2+1−x−3x−1x−12+1>0,2xx2+4−2x−1x−12+4>0,x2+1−x−12+1>0,hold for x≥3. Recall that n−k+2≥q≥3. Consequently, it holds that(10)ψq≤ψn−k+2,and hence, from (6), it follows that(11)SOG≤SOG−w+n−kn−k+22+1+2n−k+22+4−n−k−1n−k+12+1−2n−k+12+4,with equality if and only if each of the two nonpendent neighbors of v has degree 2 and n−k+2=q. Now, by using the inductive hypothesis in (11), one arrives at(12)SOG≤n−kn−k+22+1+2n−k+22+22+k−28,with equality if and only if each of the two nonpendent neighbors of v has degree 2, n−k+2=q, and G−w=Ck,n−k−1. This completes the induction and thence the proof.
In order to prove our second main result, which gives the characterization of the graphs possessing the second-maximum value of the SO index in the class of all unicyclic graphs with a fixed girth and order, we prove a series of lemmas.Lemma 3.
LetG be a connected graph of order at least 5. Let uv be an edge of G such that each of its end vertices (i) has exactly two nonpendent neighbors and (ii) contains at least one pendent neighbor provided that dGu≥dGv≥3. Let G′ be the graph obtained from G by removing all the pendent neighbors of v and then attaching them to the vertex u. It holds that SOG<SOG′.Proof.
Letv,w be the set of nonpendent neighbors of u with dGw=s≥2. Let u,w′ be the set of nonpendent neighbors of HTML translation failed with dGw′=t≥2. Also, assume that dGu=p and dGv=q. Then, p≥q≥3.(13)SOG−SOG′=p2+s2−p+q−22+s2+p−2p2+1−p+q−22+1+p2+q2−p+q−22+4+q−2q2+1−p+q−22+1+q2+t2−t2+4<q−2q2+1−p+q−22+1+q2+t2−t2+4≤q−2q2+1−4q−12+1+q2+t2−t2+4.
By Lemma1, it holds that(14)q2+t2−t2+4≤q2+4−8,and hence, (13) yields(15)SOG−SOG′<q−2q2+1−4q−12+1+q2+4−8=q2+1−4q−12+1+q2+4−8+q−3q2+1−4q−12+1≤q2+1−4q−12+1+q2+4−8<0.Lemma 4.
LetG be a connected graph of order at least 5. Let uv be an edge of G such that each of its end vertices (i) has at least one pendent neighbor and (ii) contains exactly two nonpendent neighbors such that one of them has degree 2 and dGu≥dGv≥3. (It is possible that the vertices u and v have a common neighbor.) Let G′ be the graph obtained from G by removing a pendent neighbor of v and then attaching it to u. It holds that SOG<SOG′.Proof.
LetdGu=p and dGv=q. Then, p≥q≥3. Here, one has(16)SOG−SOG′=p2+4−p+12+4+p−2p2+1−p+12+1+p2+q2−p+12+q−12+q−3q2+1−q−12+1+q2+4−q−12+4+q2+1−p+12+1<p−2p2+1−p+12+1+q−3q2+1−q−12+1+q2+4−q−12+4+q2+1−p+12+1≤q−2q2+1−q+12+1+q−3q2+1−q−12+1+q2+4−q−12+4+q2+1−q+12+1<0.Lemma 5.
LetG be a connected graph of order at least 6. Let u and v be nonadjacent vertices of G such that each of them (i) has at least one pendent neighbor and (ii) contains exactly two nonpendent neighbors such that each of them has degree 2 and dGu≥dGv≥3. Let G′ be the graph obtained from G by removing a pendent neighbor of v and then attaching it to u. It holds that SOG<SOG′.Proof.
IfdGu=p and dGv=q, then p≥q≥3, and hence, we have(17)SOG−SOG′=2p2+4−p+12+4+2q2+4−q−12+4+q−12+1−p+12+1+p−2p2+1−p+12+1+q−2q2+1−q−12+1<2p2+4−p+12+4+2q2+4−q−12+4+p−2p2+1−p+12+1+q−2q2+1−q−12+1≤2q2+4−q+12+4+2q2+4−q−12+4+q−2q2+1−q+12+1+q−2q2+1−q−12+1<0.Lemma 6.
LetG be the graph deduced from the cycle Ck of order k by attaching p pendent vertices to a vertex u∈VCk and attaching q pendent vertices to another vertex v∉u of Ck, where p≥q≥1 and p+q=n−k.(i)
Ifk=3, then(18)SOG≤n−4n−22+1+n−22+4+n−22+9+10+13,with equality if and only ifp=n−4.(ii)
If4≤k≤n−2, then(19)SOG≤n−k−1n−k+12+1+2n−k+12+4+k−48+213+10,with equality if and only if p=n−k−1 and uv∉EG.Proof.
(i)
This part follows directly from Lemma4 because uv∈EG when k=3.(ii)
Ifuv∉EG, then the desired conclusion follows from Lemma 5. In the rest of the proof, assume that uv∈EG. By Lemma 4, we have(20)SOG≤n−k−1n−k+12+1+n−k+12+4+n−k+12+9+k−38+10+13,with equality if and only if p=n−k−1. Let(21)Θ1=n−k−1n−k+12+1+2n−k+12+4+k−48+213+10,Θ2=n−k−1n−k+12+1+n−k+12+4+n−k+12+9+k−38+10+13.
Here, it holds that(22)Θ2−Θ1=n−k+12+9−n−k+12+4+8−13.
Takingp=n−k−1, we have(23)Θ2−Θ1=p+32+9−p+32+4+8−13<0,for p≥1.Lemma 7.
Forn−k−1≥q≥1 and k≤n−2, if G is the graph deduced from the unicyclic graph Ck,n−k−q (see Theorem 1) by attaching q pendent vertices to exactly one pendent vertex of Ck,n−k−q, then(24)SOG≤n−k−2n−k+12+1+3n−k+12+4+k−28+5,with equality if and only if q=1.Proof.
The result trivially holds fork=n−2 because there is only one graph in this case. Thus, we suppose that k≤n−3. Here, we have(25)SOG=n−k−q−1n−k−q+22+1+2n−k−q+22+4+n−k−q+22+q+12+k−28+qq+12+1.
The substitutionn−k=α in equation (25) yields(26)SOG=α−q−1α−q+22+1+2α−q+22+4+α−q+22+q+12+k−28+qq+12+1,where α≥q+1≥2. By a computer program, it is checked that the maximum value of the right-hand-sided expression of (26) under the given constraints is achieved if and only if q=1.
Now, we determine the graph attaining the second-maximum value of the Sombor index in the class of all unicyclic graphs with a fixed order and girth.Theorem 2.
LetG be a unicyclic graph with order n and girth g such that G≠Ck,n−k (see Theorem 1).(i)
Ifk=3, then(27)SOG≤n−22+4+n−22+9+n−4n−22+1+10+13,with equality if and only ifG is the graph deduced from C3,n−4 by attaching a pendent vertex to one of its vertices of degree 2.(ii)
If4≤k≤n−2, then(28)SOG≤k−48+2n−k+12+4+n−k−1n−k+12+1+213+10,with equality if and only if G is a graph deduced from Ck,n−k−1 by attaching a pendent vertex to a vertex  w∈VCk,n−k−1, where dCk,n−k−1w=2 and w is not adjacent to the branching neighbor.Proof.
Suppose thatv1v2…vkv1 is the unique cycle of G. Let(29)a=n−22+4+n−22+9+n−4n−22+1+10+13,whenk=3,a=k−48+2n−k+12+4+n−k+1n−k+12+1+213+10,when 4≤k≤n−2.
If the setv1,v2,…,vk contains at least three branching vertices, then by using Lemmas 2, 3 (or 5), and 6, we find a unicyclic graph G′ with order n and girth g such that G′≠Ck,n−k and satisfying SOG<SOG′≤a.
If the setv1,v2,…,vk contains exactly two branching vertices, then by using Lemmas 2, 4 (or 5), and 6, we find a unicyclic graph G″ with order n and girth g such that G″≠Ck,n−k and satisfying SOG≤SOG″≤a, where both the equality signs hold if and only if G is one of the two extremal graphs defined in the statement of the theorem.
In the remaining proof, we assume thatv1,v2,…,vk contains exactly one branching vertex; let v1 be the branching vertex. Since G≠Ck,n−k, the vertex v1 has at least three nonpendent neighbors. If v1 has either at least four nonpendent neighbors or it has only three nonpendent neighbors, each of which has at least two nonpendent neighbor, then by using Lemmas 2 and 7, we find a unicyclic graph G‴ with order n and girth g such that G‴≠Ck,n−k and satisfying SOG<SOG‴≤b, where b is the upper bound on SO given in Lemma 7, that is,(30)b=k−28+3n−k+12+4+n−k−2n−k+12+1+5.
At the end of the proof, we will prove thatb−a<0.
Ifv1 has only three nonpendent neighbors such that one of them has only one nonpendent neighbor, then from Lemma 7, it follows that SOG≤b with equality if and only if q=1.
In order to complete the proof, in the following, we prove thatb−a<0. First, we assume that k=3. Then,(31)a−b=n−22+9−2n−22+4+n−22+1+13+10−5−8>n−22+9−2n−22+4+n−22+1>0.
Now, we suppose that4≤k≤n−2. Then,(32)a−b=n−k+12+1−n−k+12+4+213+10−28−5=x2+1−x2+4+213+10−28−5>0,for x=n−k+1≥3.



---

*Source: 8202681-2022-11-08.xml*