Open AccessArticle

Ordering Unicyclic Connected Graphs with Girth g ≥ 3 Having Greatest SK Indices

Wang Hui

¹,

Adnan Aslam

Salma Kanwal

^3,*

Mahnoor Akram

³,

Tahira Sumbal Shaikh

³ and

Xuewu Zuo

General Education Department, Anhui Xinhua University, Hefei 230088, China

Department of Natural Sciences and Humanities, University of Engineering and Technology, Lahore 54000, Pakistan

Department of Mathematics, Lahore College for Women University, Lahore 54000, Pakistan

Author to whom correspondence should be addressed.

Symmetry 2023, 15(4), 871; https://doi.org/10.3390/sym15040871

Submission received: 1 March 2023 / Revised: 30 March 2023 / Accepted: 1 April 2023 / Published: 6 April 2023

(This article belongs to the Special Issue Symmetric Matrices of Graphs: Topics and Advances)

Download

Browse Figures

Figure 1
M1-transformation. "> Figure 2
M2-transformation. "> Figure 3
M3-transformation. "> Figure 4
M4-transformation. "> Figure 5
Some graph sets. "> Figure 6
Some unicyclic graphs. "> Figure 7
Unicyclic graphs having the first and second maximum <math display="inline"><semantics> <mrow> <mi>S</mi> <mi>K</mi> </mrow> </semantics></math> index when <math display="inline"><semantics> <mrow> <mi>g</mi> <mo>=</mo> <mn>3</mn> </mrow> </semantics></math>. "> Figure 8
Graphs with the greatest <math display="inline"><semantics> <mrow> <mi>S</mi> <mi>K</mi> </mrow> </semantics></math> index. "> Figure 9
Unicyclic connected graphs having the greatest <math display="inline"><semantics> <mrow> <mi>S</mi> <mi>K</mi> </mrow> </semantics></math> index. "> Figure 10
Unicyclic connected graphs having greatest <math display="inline"><semantics> <mrow> <mi>S</mi> <msub> <mrow> <mi>K</mi> </mrow> <mrow> <mn>1</mn> </mrow> </msub> </mrow> </semantics></math> and <math display="inline"><semantics> <mrow> <mi>S</mi> <msub> <mrow> <mi>K</mi> </mrow> <mrow> <mn>2</mn> </mrow> </msub> </mrow> </semantics></math> indices. "> Figure 11
Unicyclic connected graphs having the greatest SK index. "> Figure 12
Molecular structures in chemistry. ">

Versions Notes

Abstract

For a graph, the SK index is equal to the half of the sum of the degrees of the vertices, the SK₁ index is equal to the half of the product of the degrees of the vertices, and the SK₂ index is equal to the half of the square of the sum of the degrees of the vertices. This paper shows a simple and unified approach to the greatest SK indices for unicyclic graphs by using some transformations and characterizes these graphs with the first, second, and third SK indices having order r ≥ 5 and girth g ≥ 3, where girth is the length of the shortest cycle in a graph.

Keywords:

SK indices; graph transformations; girth; pendant vertex; unicyclic graphs

1. Background Survey and Preliminary Results

In this paper, the term “graph” will always mean a simple, finite, and undirected graph. A graph [1] is an ordered pair

A = (V (A), E (A))

which is a representation of vertex set

V (A)

and edge set

E (A)

. Here,

A

is taken as a unicyclic connected graph having order

r

and size

e

. Let the degree of a vertex

ω

be denoted by

d_{A} (ω)

whereas the distance between two vertices

ω

and

x

be denoted by

d (ω, x)

. If

d (ω) = 1

then

ω

is said to be a leaf or pendant vertex.

A graph invariant is a numerical parameter for the characterization of the topology of a graph which is calculated on the basis of a molecular graph of a chemical compound. Some invariants are degree based and some are based on distance.

For constructing relationships between the physical, chemical and biological characteristics and the arrangements of molecules in a chemical compound, the most useful tool is chemical invariants. These invariants are symmetric functions and provide us with a chance to examine or investigate the physical and chemical properties of molecules in a compound without the expenditure of money and time used in testing in a laboratory [2].

The most former topological index introduced by Harold Wiener is the Wiener index [3] which is expressed as

W (A) = \sum_{{ω, x} \subseteq V (A)} d_{A} (ω, x)

(1)

i.e., the total of the distances between all of A’s unordered vertex pairs. Gutman and Trinajstić [4] established the first degree-based topological indices, the Zagreb indices, more than 30 years ago. Balaban et al. named them the Zagreb group indices after 10 years. It was later reduced to the Zagreb index [5,6].

The first Zagreb index and second Zagreb indexare defined as

M_{1} (A) = \sum_{ω x \in E (A)} (d (ω) + d (x)) = \sum_{ω \in V (A)} (d (ω))^{2}

(2)

M_{2} (A) = \sum_{ω, x \in E (A)} (d (ω) d (x))

(3)

In 2016, Shigehalli and Kanabur [7] put forward the new degree-based graph invariants. These are presented as

S K (A) = \sum_{ω x \in E (A)} \frac{d (ω) + d (x)}{2}

(4)

S K_{1} (A) = \sum_{ω x \in E (A)} \frac{d (ω) d (x)}{2}

(5)

S K_{2} (A) = \sum_{ω x \in E (A)} [\frac{d (ω) + d (x)}{2}]^{2}

(6)

In the last 30 years, many researchers and scholars have been working on the chemical graph theory. Many authors worked on these connectivity indices.

Shigehalli et al. [7] computed SK indices of the

H

-naphtalenic nanotube and the

T \cup C_{4} [m, n]

nanotube. In [8], Shigehalli et al. obtained the explicit formulas without the aid of a computer for the polyhex nanotube. In [9],

S K

indices first appeared and also their explicit formula for Graphene was obtained. In [10], Shin Min Kang et al. calculated

S K

and some other indices of Porphyrin, Zinc-Porphyrin, Propyl Ether Imine, and Poly Dendrimers and also plotted them using Maple software. In [11], Ranjini and Lokeshacalculated the

S K

Indices of a graph operator subdivision graph

S (G)

and semi-total point graph

R (G)

on certain important chemical structures like tetracenic nanotubes and tetracenicnanotori. In [12], the behaviors of

S K, {S K}_{1}

and

{S K}_{2}

indices were investigated under some graphoperations by Nurkahli and Buyukkose. In [13], Roy and Ghosh concluded that the

E T A

descriptors were sufficiently rich in chemical information to encode the structural features contributing to the toxicities and these indices might be used in combination with other topological and physicochemical descriptors for the development of predictive

Q S A R

models. Recently, Lokesha et al. [14] established the

S K

indices of carbon nanocones using a

Q (A)

operator. In [15], thegeneralized prism network of

S K

indices was investigated. In [16], Harisha et al. calculated the SK indices of the semi-total point graph

R (G)

and subdivision graph

S (G)

on tetracenic nanotubes and tetracenicnanotori, two significant chemical structures. In [17], the behaviors of

S K

indices were investigated under some graph operations when defined on weighted and interval weighted graphs.

1.1. Some Graph Transformations

2014

, Tomescu et al. [18] used first and defined other three graph transformations to find the minimum, second and third minimum general sum connectivity indices of unicyclic connected graphs having fixed order and girth. These transformations are listed below.

M_{1} - t r a n s f o r m a t i o n

: In general, let

y z

be an edge whose vertices

y

and

z

have no common neighbor in a connected graph, where

d (y), d (z) \geq 2

. Furthermore, let

M_{1} (A)

be the graph obtained by deleting an edge

y z

, identifying

y

and

z

in a new vertex

t

and adding a pendant edge to it.

In particular, let there be a connected unicyclic graph

A

with two nearby vertices

ω_{i}, ω_{i + 1}

having no common neighbor in

A

, such that

μ

and

ν

pendant edges are linked to

ω_{i}

and

ω_{i + 1}

with

d (ω_{i}) = μ + 2

and

d (ω_{i + 1}) = ν + 2,

respectively, where

d (ω_{i}, ω_{i + 1}) \geq 2

. Then, the graph obtained by contracting edge

ω_{i} ω_{i + 1}

and attaching a new pendant edge to vertex

ω_{i}

M_{1} (A)

. (See Figure 1).

M_{2} - t r a n s f o r m a t i o n

: Let

ω_{i}, ω_{i + 1}

be the neighboring vertices with pendant edges such that

d (ω_{i}) = μ + 2

d (ω_{i + 1}) = ν + 2

in a connected unicyclic graph

A

where

μ, ν \geq 1

. Furthermore, after removing all the pendant edges incident to

ω_{i}

and attaching them to

ω_{i + 1}

, we obtained a graph

M_{2} (A)

(see Figure 2).

M_{3} - t r a n s f o r m a t i o n

: Let

A

be a unicyclic graph with vertices

ω_{i}, ω_{j}

such that their distance

d (ω_{i}, ω_{j}) \geq 2

where

d (ω_{i}) = μ + 2

d (ω_{j}) = ν + 2

;

1 \leq μ \leq ν

. Then, the graph we have after deleting one pendant edge from

ω_{i}

and adding it to

ω_{j}

M_{3} (A)

(see Figure 3).

M_{4} - t r a n s f o r m a t i o n

: Let

ω_{i}, ω_{i + 1}

be neighboring vertices of a unicyclic connected graph

A

such that

d (ω_{i}) = μ + 2

d (ω_{i + 1}) = ν + 2; 1 \leq μ \leq ν

. By

M_{4} - transformation

, the graph

M_{4} (A)

is attained by separating one pendant edge from

ω_{i}

and connecting it to

ω_{i + 1}

(see Figure 4).

1.2. Certain Unicyclic Graphic Structures

Let a unicyclic graph

U_{r} (μ)

which is deduced from

X (r - μ, 3; r - μ - 3,0, 0)

by adding

μ

pendant edges to a pendant vertex of it, where

1 \leq μ \leq r - 4

Let the set of unlabelled connected unicyclic graphs be denoted by

O_{r, g}

having order

r

and girth

g

where

r \geq g \geq 3

. A unicyclic graph

X (r, g; r_{1}, r_{2}, \dots, r_{g})

with

r_{i} \geq 0

is obtained by joining the

r_{i}

pendant edges to a vertex

ω_{i}; 1 \leq i \leq g

of cycle

C_{g} = ω_{1}, ω_{2}, \dots, ω_{g}, ω_{1}

where

r_{1} + r_{2} + \dots + r_{g} = r - g

. Moreover,

X_{r, g} = X (r, g; r - g, 0, \dots, 0)

(see Figure 5).

We will also use two sets of unicyclic connected graphs:

(i): $Y (r, g)$ is the family of unicyclic graphs in which the $r - g - 1$ pendant edges are incident to a vertex $ω \in V (C_{g})$ and one pendant edge to $x \in V (C_{g})$ , where $d (ω, x) \geq 2$ .
(ii): $Z (r, g)$ is the set of unicyclic graphs in which the $r - g - 2$ pendant edges are incident to $ω$ and two pendant edges are incident to $x$ , where $d (ω, x) \geq 2$ .

Y (r, g)

and

Z (r, g)

, all graphs have similar index and properties. If

E \in Y_{r, g}

and

F \in Z_{r, g}

then

E = M_{3} (F)

. Moreover, we will utilize six different kinds of graphs to prove our main result, that are defined below:

(i): $A_{1} = X (r, g; μ - 1,1, 0, \dots, 0)$ where $μ = r - g \geq 2$ .
(ii): $A_{2} = X (r, g; μ - 2,0, 2,0, \dots, 0)$ where $μ = r - g \geq 2$ . It can be easily seen that $A_{2} \in Z_{r, g}$ .
(iii): $A_{3} = X (r, g; μ - 1,0, 1,0, \dots, 0) .$
(iv): $A_{4}$ : It is deduced by attaching one pendant edge to a pendant vertex of $X (r - 1, g; μ - 1,0, \dots, 0)$
(v): $A_{5}$ : It is obtained by connecting the $μ - 1$ pendant edges to the pendant vertex of $X (r - μ + 1, g; 1,0, \dots, 0)$ .
(vi): $A_{6} = X (r, g; μ - 2,2, 0, \dots, 0) .$

(See Figure 6.)

In this paper, we study three maximum

S K

indices,

i . e ., S K (A)

S K_{1} (A)

and

S K_{2} (A)

in a unicyclic connected graph

A

having order

r \geq 5

and girth

g \geq 3

2. Ordering Unicyclic Structures with the Greatest SK Index

In this section, we use some graph transformations which increase the

S K

index.

Lemma 1.

Let

M_{1} (A)

be a unicyclic connected graph as shown in Figure 1, then

S K (A) < S K (M_{1} (A))

for any

μ, v \geq 0

Proof.

Case 1: Ref. [19] When

M_{1}

is performed excluding the vertices of

C_{g}

\begin{array}{l} S K (A) - S K (M_{1} (A)) & = \frac{1}{2} \sum_{x y \in E (A) \ {y z}} [(d_{x} + d_{y}) - (d_{x} + d_{y} + d_{z} - 1)] \\ + \frac{1}{2} \sum_{x z \in E (A) \ {y z}} [(d_{x} + d_{z}) - (d_{x} + d_{y} + d_{z} - 1)] < 0; a s d_{y} \geq 2 \end{array}

Case 2: When

M_{1}

is performed on the vertices of

C_{g}

We have

d_{A} (ω_{i}) = d_{M_{1} (A)} (ω_{i}) - v - 1 < d_{M_{1} (A)} (ω_{i})

and

d_{M_{1} (A)} (ω_{i}) + d_{M_{1} (A)} (ω_{i + 1}) = μ + v + 4

Therefore, for

j = \bar{1, μ} = 1,2, \dots, μ

k = \bar{1, v} = 1,2, \dots, v

and by the definition of

S K

index, we find

\begin{array}{l} S K (A) - S K (M_{1} (A)) & = \frac{1}{2} [{d (ω_{i - 1}) + d (ω_{i})} + μ {d (ω_{i, j}) + d (ω_{i})} + {d (ω_{i}) \\ + d (ω_{i + 1})} + ν {d (ω_{i + 1, k}) + d (ω_{i + 1})} + {d (ω_{i + 1}) + d (ω_{i + 2})}] \\ = \frac{1}{2} [{d (ω_{i - 1}) + d (ω_{i})} + (μ + ν + 1) {d (ω_{i, l}) + d (ω_{i})} \\ {d (ω_{i}) + d (ω_{i + 2})}] \\ = - (μ + ν + μ ν + 1) < 0 f o r μ, ν \geq 0 . \end{array}

\Rightarrow S K (A) < S K (M_{1} (A)) □

Lemma 2.

Let

M_{2} (A)

be a unicyclic connected graph as depicted in Figure 2, where

d_{A} (ω_{i}, ω_{i + 1}) = 1

. Then

S K (A) < S K (M_{2} (A))

for any

v \geq μ \geq 1

Proof.

Since

d_{M_{2} (A)} (ω_{i}) = 2 < d_{A} (ω_{i}) = μ + 2

and

d_{A} (ω_{i + 1}) = ν + 2 < d_{M_{2} (A)} (ω_{i + 1}) = ν + μ + 2

\begin{array}{l} S K (A) - S K (M_{2} (A)) & = \frac{1}{2} [{d (u_{i - 1}) + d (u_{i})} + \sum_{j = 1}^{μ} \\ {d (ω_{i, j}) + d (ω_{i})} + {d (ω_{i}) + d (ω_{i + 1})} \\ + \sum_{k = 1}^{ν} {d (ω_{i + 1, k}) + d (ω_{i + 1})} + {d (ω_{i + 1}) + d (ω_{i + 2})}] - \frac{1}{2} [{d (ω_{i - 1}) \\ + d (ω_{i})} + {d (ω_{i}) + d (ω_{i + 1})} + (μ + ν) {d (ω_{i, j}) + d (ω_{i + 1})} \\ + {d (ω_{i + 1}) + d (ω_{i + 2})}] \\ = \frac{1}{2} [{d (ω_{i - 1}) + d (ω_{i})} + μ {d (ω_{i, j}) + d (ω_{i})} + {d (ω_{i}) + d (ω_{i + 1})} \\ + ν {d (ω_{i + 1, k}) + d (ω_{i + 1})} + {d (ω_{i + 1}) + d (ω_{i + 2})}] - \frac{1}{2} [{d (ω_{i - 1}) \\ + d (ω_{i})} + {d (ω_{i}) + d (ω_{i + 1})} + (μ + ν) {d (ω_{i, j}) + d (ω_{i + 1})} \\ + {d (ω_{i + 1}) + d (ω_{i + 2})}] \\ = \frac{1}{2} {(2 + μ + 2) + μ (1 + μ + 2) + (μ + 2 + ν + 2) + ν (1 + ν + 2) \\ + (ν + 2 + 2)} - \frac{1}{2} {(2 + 2) + (2 + μ + ν + 2) \\ + (μ + ν) (1 + μ + ν + 2) + (μ + ν + 2 + 2)} \\ = - μ ν < 0 f o r ν \geq μ \geq 1 . \end{array}

\Rightarrow S K (A) < S K (M_{2} (A)) □

Lemma 3.

Let

M_{3} (A)

be a unicyclic connected graph as presented in Figure 3, where

d_{A} (ω_{i}, ω_{i + 1}) = d_{M_{3} (A)} (ω_{i}, ω_{i + 1}) \geq 2

. Then

S K (A) < S K (M_{3} (A)); v \geq μ \geq 1

Proof.

Following the previous lemma and by the definition of

S K (A)

we find

\begin{array}{l} S K (A) - S K (M_{3} (A)) & = \frac{1}{2} [{d (ω_{i - 1}) + d (ω_{i})} + \sum_{k = 1}^{μ} {d (ω_{i, j}) + d (ω_{i})} + {d (ω_{i}) + d (ω_{i + 1})} \\ + {d (ω_{i + 1}) + d (ω_{j})} + \sum_{l = 1}^{ν} {d (ω_{j, ν}) + d (ω_{j})} + {d (ω_{j}) + d (ω_{j + 1})}] \\ - \frac{1}{2} [{d (ω_{i - 1}) + d (ω_{i})} + \sum_{k = 1}^{μ - 1} {d (ω_{i, μ - 1}) + d (ω_{i})} + {d (ω_{i}) \\ + d (ω_{i + 1})} + {d (ω_{i + 1}) + d (ω_{j})} + \sum_{l = 1}^{ν + 1} {d (ω_{j, ν}) + d (ω_{j})} \\ + {d (ω_{j}) + d (ω_{j + 1})}] \\ = \frac{1}{2} [{d (ω_{i - 1}) + d (ω_{i})} + μ {d (ω_{i, j}) + d (ω_{i})} + {d (ω_{i}) + d (ω_{i + 1})} \\ + {d (ω_{i + 1}) + d (ω_{j})} + ν {d (ω_{j, ν}) + d (ω_{j})} + {d (ω_{j}) + d (ω_{j + 1})}] \\ - \frac{1}{2} [{d (ω_{i - 1}) + d (ω_{i})} + (μ - 1) {d (ω_{i, μ - 1}) + d (ω_{i})} + {d (ω_{i}) \\ + d (ω_{i + 1})} + {d (ω_{i + 1}) + d (ω_{j})} + (ν + 1) {d (ω_{j, ν}) + d (ω_{j})} \\ + {d (ω_{j}) + d (ω_{j + 1})}] \\ = \frac{1}{2} {(2 + μ + 2) + μ (1 + μ + 2) + (μ + 2 + 2) + (2 + ν + 2) \\ + ν (1 + ν + 2) + (ν + 2 + 2)} - \frac{1}{2} {2 + μ - 1 + 2 + (μ - 1) \\ (1 + μ - 1 + 2) + (μ - 1 + 2 + 2) + (2 + 1 + ν + 2) \\ + (ν + 1) (1 + ν + 1 + 2) + (ν + 1 + 2 + 2)} \\ = μ - (ν + 1) < 0 ν \geq μ \geq 1 \end{array}

\Rightarrow S K (A) < S K (M_{3} (A)) □

Hence, the proof is complete.

Lemma 4.

Let

M_{4} (A)

be the connected unicyclic graph as illustrated in Figure 4. For any

v \geq μ \geq 1

, we have

S K (A) < S K (M_{4} (A))

Proof.

d_{A} (ω_{i}, ω_{i + 1}) = 1

then

d_{M_{4} (A)} (ω_{i}) + d_{M_{4} (A)} (ω_{i + 1}) = μ + 2 + ν + 2 = d_{A} (ω_{i}) + d_{A} (ω_{j})

and by the definition of

S K (A),

we have

\begin{array}{l} S K (A) - S K (M_{3} (A)) & = \frac{1}{2} [{d (ω_{i - 1}) + d (ω_{i})} + \sum_{k = 1}^{μ} {d (ω_{i, j}) + d (ω_{i})} + {d (ω_{i}) + d (ω_{i + 1})} \\ + {d (ω_{i + 1}) + d (ω_{j})} + \sum_{l = 1}^{ν} {d (ω_{j, ν}) + d (ω_{j})} + {d (ω_{j}) + d (ω_{j + 1})}] \\ - \frac{1}{2} [{d (ω_{i - 1}) + d (ω_{i})} + \sum_{k = 1}^{μ - 1} {d (ω_{i, μ - 1}) + d (ω_{i})} + {d (ω_{i}) \\ + d (ω_{i + 1})} + {d (ω_{i + 1}) + d (ω_{j})} + \sum_{l = 1}^{ν + 1} {d (ω_{j, ν}) + d (ω_{j})} \\ + {d (ω_{j}) + d (ω_{j + 1})}] \\ = \frac{1}{2} [{d (ω_{i - 1}) + d (ω_{i})} + μ {d (ω_{i, j}) + d (ω_{i})} + {d (ω_{i}) + d (ω_{i + 1})} \\ + {d (ω_{i + 1}) + d (ω_{j})} + ν {d (ω_{j, ν}) + d (ω_{j})} + {d (ω_{j}) + d (ω_{j + 1})}] \\ - \frac{1}{2} [{d (ω_{i - 1}) + d (ω_{i})} + (μ - 1) {d (ω_{i, μ - 1}) + d (ω_{i})} + {d (ω_{i}) \\ + d (ω_{i + 1})} + {d (ω_{i + 1}) + d (ω_{j})} + (ν + 1) {d (ω_{j, ν}) + d (ω_{j})} \\ + {d (ω_{j}) + d (ω_{j + 1})}] \\ = \frac{1}{2} {(2 + μ + 2) + μ (1 + μ + 2) + (μ + 2 + 2) + (2 + ν + 2) \\ + ν (1 + ν + 2) + (ν + 2 + 2)} - \frac{1}{2} {2 + μ - 1 + 2 + (μ - 1) \\ (1 + μ - 1 + 2) + (μ - 1 + 2 + 2) + (2 + 1 + ν + 2) \\ + (ν + 1) (1 + ν + 1 + 2) + (ν + 1 + 2 + 2)} \\ = μ - (ν + 1) < 0 ν \geq μ \geq 1 \end{array}

\Rightarrow S K (A) < S K (M_{4} (A)) □

Now, first we find the extremal graphs having the greatest value and then give an ordering of the unicyclic connected graphs in decreasing order for the

S K

index.

Theorem 1.

Ref. [19] Let

X (r, 3; a, b, c)

;

a + b + c = r - 3

;

a \geq b \geq c \geq 1

be a set of unicyclic connected graphs with

r \geq 5

. Then, the first maximum and second maximum values of the

S K

index are attained by

X (r, 3; r - 3,0, 0)

and

X (r, 3; r - 4,1, 0),

respectively,

i . e .,

\begin{array}{l} S K (X (r, 3; r - 4,1, 0)) < S K (X (r, 3; r - 3,0, 0)) \end{array}

(See Figure 7.)

Proof.

We need only to prove

S K (X (r, 3; a, b, c)) < S K (X (r, 3; a + 1, b - 1, c))

. Consider

\begin{array}{l} S K (X (r, 3; a, b, c)) - S K (X (r, 3; a + 1, b - 1, c)) \\ = \frac{1}{2} {a (1 + a + 2) + (a + 2 + b + 2) + b (1 + b + 2) + (b + 2 + c + 2) + c (1 + c + 2) \\ + (c + 2 + a + 2)} - \frac{1}{2} {(a + 1) (1 + a + 1 + 2) + (a + 1 + 2 + b - 1 + 2) \\ + (b - 1) (1 + b - 1 + 2) + (b - 1 + 2 + c + 2) + c (1 + c + 2) + (c + 2 + a + 1 + 2)} \\ = - a + b - 1 < 0 f o r a \geq b \geq c \geq 1 . \end{array} □

Hence, the result follows.

Lemma 5.

Ref. [19] If

S K (U_{r} (μ))

is the maximum for fixed

r \geq 5

, where

1 \leq μ \leq r - 4

, then we have

μ = 1

r - 4

Proof.

For

r = 5

μ = 1 = r - 4

and there is only one graph

U_{5} (1)

. So, there cannot be a debate in choosing the maximum or minimum. Suppose that

3 \leq μ \leq r - 5

\begin{array}{l} S K (U_{r} (μ)) & = \frac{1}{2} {2 (2 + r - μ - 4 + 3) + (r - μ - 4) (1 + r - μ - 4 + 3) + (r - μ - 4 \\ + 3 + μ + 1) + μ (1 + μ + 1) + (2 + 2)} = \frac{1}{2} (r^{2} + 2 μ^{2} - r + 4 μ - 2 r μ + 6) \end{array}

\begin{array}{l} S K (U_{r} (μ + 1)) = \frac{1}{2} (r^{2} + 2 μ^{2} + r + 4 μ - 2 r μ + 10) \end{array}

By using the above calculations, we determine

S K (U_{r} (μ + 1)) - S K (U_{r} (μ)) = r + 2 > 0

\Rightarrow S K (U_{r} (μ + 1)) > S K (U_{r} (μ))

concluding that

S K (U_{r} (r - 4)) > S K (U_{r} (μ))

where

S K (U_{r} (r - 4)) = \frac{1}{2} (r^{2} - 5 r + 22)

For

μ = 1,2

, we have

\begin{array}{l} S K (U_{r} (1)) = \frac{1}{2} (r^{2} - 3 r + 12) \end{array}

\begin{array}{l} S K (U_{r} (2)) = \frac{1}{2} (r^{2} - 5 r + 22) \end{array}

Furthermore

S K (U_{r} (1)) - S K (U_{r} (2)) = r - 5 > 0

S K (U_{r} (1)) - S K (U_{r} (r - 4)) = r - 5 > 0

S K (U_{r} (2)) - S K (U_{r} (r - 4)) = 0

By the above inequalities, we have

S K (U_{r} (1)) > S K (U_{r} (2)) = S K (U_{r} (r - 4)) > S K (U_{r} (μ)), U_{r} (μ); 3 \leq μ \leq r - 5

The above used graphs are shown in Figure 8.

So,

U_{r} (1)

is the graph with the first maximum and

U_{r} (2)

and

U_{r} (r - 4)

with the second maximum

S K

index, and we are complete. □

Theorem 2.

Let

A

having girth

g

with

4 \leq g \leq r

, be a connected unicyclic graph. Then

S K (A) \leq S K (X_{r, g})

where

X_{r, g} = X (r, g; r - g, 0, \dots, 0)

Proof.

Let

A \in O_{r, g}

, where

O_{r, g}

be the set of unlabeled connected unicyclic graphs having order

r

and girth

g

with

r \geq g > 3

. If

g = r

, then

A = C_{g}

; for

g = r - 1

then

A = X (r, r - 1; 1,0, \dots, 0)

. Suppose that

3 \leq g \leq r - 2

and

A

has the largest

S K

index.

A

is a graph with some vertex disjoint trees having each a common vertex with

C_{g}

. After applying

M_{1}

-transformation, the trees are reduced to some stars with centers on

C_{g}

and the

S K

index strictly increases by Lemma 1. Since

S K (A)

is the maximum, it implies that

A = X (r, g; r_{1}, \dots, r_{g})

where

r_{1}, \dots, r_{g} \geq 0

and

r_{1} + \dots + r_{g} = r - g

. All the pendant edges attached at the vertices of

C_{g}

are made incident to the unique and same vertex. After applying

M_{2}, M_{3}

-transformations several times, that would give

A = X_{r, g} = X (r, g; r - g, 0, \dots, 0)

. □

Remark 1.

r - 1 \geq g \geq 3

then

S K (X (r, g; r - g, 0, \dots, 0)) > S K (X (r, g + 1; r - g - 1,0, \dots, 0))

by Case 1 of Lemma 1.

Lemma 6.

For

p = r - g \geq 2

, we have

(a): $S K (A_{2}) < S K (A_{1})$
(b): $S K (A_{3}) = S K (A_{1})$
(c): $S K (A_{4}) < S K (A_{1})$
(d): $S K (A_{5}) < S K (A_{1})$

(See Figure 8.)

Proof.

\begin{array}{l} (a) S K (A_{2}) - S K (A_{1}) \\ = \frac{1}{2} {(2 + μ - 2 + 2) + (μ - 2) (1 + μ - 2 + 2) + (μ - 2 + 2 + 2) + (2 + 4) + (4 + 2) \\ + (4 + 2)} - \frac{1}{2} {(2 + μ - 1 + 2) + (μ - 1) (1 + μ - 1 + 2) + (μ - 1 + 2 + 3) + (3 + 1) \\ + (3 + 2) + (2 + 2)} = - μ + 1 < 0 . \end{array}

\begin{array}{l} (b) S K (A_{3}) - S K (A_{1}) \\ = \frac{1}{2} {(μ - 1) (1 + μ - 1 + 2) + (μ - 1 + 2 + 2) + (2 + 3) + (3 + 1) + (3 + 2)} \\ - \frac{1}{2} {(μ - 1) (1 + μ - 1 + 2) + (μ - 1 + 2 + 3) + (3 + 1) + (3 + 2) + (2 + 2)} = 0 . \end{array}

\begin{array}{l} (c) S K (A_{4}) - S K (A_{1}) \\ = \frac{1}{2} {(2 + μ - 1 + 2) + (μ - 2) (1 + μ - 2 + 3) + (μ - 2 + 3 + 2) + (2 + 1) + (μ - 1 + 2 + 2) \\ + (2 + 2)} - \frac{1}{2} {(2 + μ - 1 + 2) + (μ - 1) (1 + μ - 1 + 2) + (μ - 1 + 2 + 3) + (3 + 1) \\ + (3 + 2)} = - 1 < 0 . \end{array}

\begin{array}{l} (d) S K (A_{5}) - S K (A_{1}) \\ = \frac{1}{2} {(2 + 3) + (3 + μ - 1 + 1) + (μ - 1) (1 + μ - 1 + 1) + (3 + 2) + (2 + 2)} \\ - \frac{1}{2} {(2 + μ - 1 + 2) + (μ - 1) (1 + μ - 1 + 2) + (μ - 1 + 2 + 3) + (3 + 1) + (3 + 2)} = - μ + 1 < 0 . \end{array} □

Theorem 3.

(a) Let

A \in O_{r, g} \ {X_{r, g}}

, where

r \geq 6, (4 \leq g \leq r - 2)

. Then

A

has a maximum

S K

index if, and only if,

A = A_{1} (= A_{3})

(b) Let

A \in O_{r, g} \ {(A_{1} \cup X_{r, g})}

, where

r \geq 6, (4 \leq g \leq r - 2)

. Then

A

has a maximum

S K

index if, and only if,

A = X (r, g; r - g - 2,0, 2,0, \dots, 0) = A_{2}

Proof.

Let

A \in O_{r, g}

be a connected unicyclic graph having the second or third maximum

S K

index. Suppose that there is a vertex with a degree of at least 3 in a cycle

C_{g}

A

. Since

A \neq X_{r, g}

, then there is at least one non-pendant vertex in

C

Case 1: When there is exactly one non-pendant vertex outside

C

, we obtained

A

by attaching the

μ

pendant edges to a pendant vertex of

X (r - μ, g; r - g - μ, 0, \dots, 0)

where

(1 \leq μ \leq r - g - 1)

. Lemma 5 states that for

μ = 1

r - 4

we have a maximum of

S K (U_{r} (μ))

with corresponding graphs

A_{4}

and

A_{5}

, respectively.

However, Lemma 6 implies that the graphs with the second or third maximum

S K

index cannot be

A_{4}

A_{5}

Case 2: When there are at least two non-pendant vertices outside

C,

after the continuous application of

M_{1}

-transformation, we have

S K (A) < m a x {S K (A_{4}), S K (A_{5})} < S K (A_{3}) = S K (A_{1}) < S K (X_{r, g})

as S K (A_{1}) - S K (X_{r, g}) = {\frac{1}{2} (r^{2} + g^{2} + 3 r + g - 2 r g + 2)} - {\frac{1}{2} (r^{2} + g^{2} + 5 r - g - 2 r g)} = - r + g + 1 < 0

(7)

Thus, we knew that if

A

has a second or third maximum

S K

index then the two vertices on

C_{g}

must exist having a degree of at least three.

(a) For

A \neq X_{r, g}

, if

A

has a maximum

S K

then

C_{g}

cannot have three vertices with a degree of at least 3.

We obtained

X_{r, g}

after several applications of

M_{i}

-transformations

(i \geq 1)

. However, we found a graph with an index less than

X_{r, g}

, we see that

S K (A) < m a x {S K (A_{3}), S K (A_{1})} = S K (A_{3}) = S K (A_{1}) < S K (X_{r, g})

It implies that

A

has exactly two vertices

m, n

C_{g}

having a degree of at least 3.

Degrees of

m

and

n

must be as:

d (m) = r - g + 1, d (n) = 3

, since other cases cannot hold because if

d (m) = 2

then

A

becomes

X_{r, g}

(since our supposition of the degree is at least

3

) and if

d (m) = 4

then

A

cannot become the second maximum because

A

with

d (m) = 3

has a greater index than

A

with

d (m) = 4

Now, if

d (m, n) = 1

then

A = A_{1}

and if

d (m, n) \geq 2

then

A \in Y (r, g)

class including

A_{3}

Lemma 6 implies that, in this case, extremal graph is

A_{1}

(b) For

A \in O_{r, g} \ (A_{1} \cup X_{r, g})

, by the same argument we deduce that

C_{g}

cannot have three vertices with a degree of at least 3, if

A

has a maximum

S K

index, since, in this case, we would have

S K (A) < S K (A_{2}) < S K (A_{3}) = S K (A_{1}) < S K (X_{r, g})

as S K (A_{2}) - S K (A_{1}) = \{\frac{1}{2} (r^{2} + g^{2} + r + 3 g - 2 r g + 4)\} - \{\frac{1}{2} (r^{2} + g^{2} + 3 r + g - 2 r g + 2)\}

= \frac{1}{2} (- 2 r + 2 g + 2) = - r + g + 1 < 0

It implies that

A

has exactly two vertices

a, b

C_{g}

having a degree of at least 3.

By the same argument (used above),

d (m) = r - g

and

d (n) = 4

d (m, n) = 1

then

A = A_{6}

and if

d (m, n) \geq 2

then

A \in Z (r, g)

class including

A_{2}

, which ends the proof(see Figure 9). □

3. Ordering Unicyclic Structures with the Greatest SK₁ Index

In this section, we use graph transformations which increase the

S K_{1}

index.

Lemma 7.

Let

M_{1} (A)

be a unicyclic connected graph as shown in Figure 1, then

S K_{1} (A) < S K_{1} (M_{1} (A))

for any

μ, v \geq 0

Proof.

Case 1: Ref. [19] When

M_{1}

is performed excluding vertices of

C_{g}

\begin{array}{l} S K_{1} (A) - S K_{1} (M_{1} (A)) & = \frac{1}{2} \sum_{x y \in E (A) \ {y z}} [(d_{x} . d_{y}) - (d_{x}) (d_{y} + d_{z} - 1)] \\ + \frac{1}{2} \sum_{x z \in E (A) \ {y z}} [(d_{x} . d_{z}) - (d_{x}) (d_{y} + d_{z} - 1)] < 0; a s d_{y} \geq 2 \end{array}

Case 2: When

M_{1}

is performed on vertices of

C_{g}

We have

d_{A} (ω_{i}) = d_{M_{1} (A)} (ω_{i}) - v - 1 < d_{M_{1} (A)} (ω_{i})

and

d_{M_{1} (A)} (ω_{i}) + d_{M_{1} (A)} (ω_{i + 1}) = μ + v + 4

Therefore, for

j = \bar{1, μ} = 1,2, \dots, μ

k = \bar{1, v} = 1,2, \dots, v

and by the definition of the

S K_{1}

index, we find

\begin{array}{l} S K_{1} (A) - S K_{1} (M_{1} (A)) & = \frac{1}{2} [{d (ω_{i - 1}) . d (ω_{i})} + μ {d (ω_{i, j}) . d (ω_{i})} + {d (ω_{i}) . d (ω_{i + 1})} \\ + ν {d (ω_{i + 1, k}) . d (ω_{i + 1})} + {d (ω_{i + 1}) . d (ω_{i + 2})}] - \frac{1}{2} [{d (ω_{i - 1}) . d (ω_{i})} \\ + (μ + ν + 1) {d (ω_{i, j}) . d (ω_{i})} + {d (ω_{i}) . d (ω_{i + 2})}] \\ = \frac{1}{2} [{(2) (μ + 2)} + μ {(1) (μ + 2)} {(μ + 2) (ν + 2)} \\ + ν {(1) (ν + 2)} + {(ν + 2) (2)}] - \frac{1}{2} [{(2) (μ + ν + 3)} \\ + (μ + ν + 1) {(1) (μ + ν + 3)} + {(μ + ν + 3) (2)}] \\ = - {μ + ν + \frac{1}{2} (3 + μ ν)} < 0 f o r μ, ν \geq 1 . \end{array}

\Rightarrow S K_{1} (A) < S K_{1} (M_{1} (A)) □

Lemma 8.

Let

M_{2} (A)

be a unicyclic connected graph as depicted in Figure 2, where

d_{A} (ω_{i}, ω_{i + 1}) = 1

. Then

S K_{1} (A) < S K_{1} (M_{2} (A))

for any

v \geq μ \geq 1

Proof.

Since

d_{M_{2} (A)} (ω_{i}) = 2 < d_{A} (ω_{i}) = μ + 2

and

d_{A} (ω_{i + 1}) = ν + 2 < d_{M_{2} (A)} (ω_{i + 1}) = ν + μ + 2

\begin{array}{l} S K_{1} (A) - S K_{1} (M_{2} (A)) & = \frac{1}{2} [{d (ω_{i - 1}) . d (ω_{i})} + \sum_{j = 1}^{μ} {d (ω_{i, j}) . d (ω_{i})} + {d (ω_{i}) . d (ω_{i + 1})} \\ + \sum_{k = 1}^{ν} {d (ω_{i + 1, k}) . d (ω_{i + 1})} + {d (ω_{i + 1}) . d (ω_{i + 2})}] \\ \frac{1}{2} [{d (ω_{i - 1}) . d (ω_{i})} + {d (ω_{i}) . d (ω_{i + 1})} + (μ + ν) {d (ω_{i, j}) . d (ω_{i + 1})} \\ + {d (ω_{i + 1}) . d (ω_{i + 2})}] \\ = \frac{1}{2} [{d (ω_{i - 1}) . d (ω_{i})} + μ {d (ω_{i, j}) . d (ω_{i})} + {d (ω_{i}) . d (ω_{i + 1})} \\ + ν {d (ω_{i + 1, k}) . d (ω_{i + 1})} + {d (ω_{i + 1}) . d (ω_{i + 2})}] \\ \frac{1}{2} [{d (ω_{i - 1}) . d (ω_{i})} + {d (ω_{i}) . d (ω_{i + 1})} + (μ + ν) {d (ω_{i, j}) . d (ω_{i + 1})} \\ + {d (ω_{i + 1}) . d (ω_{i + 2})}] \\ = \frac{1}{2} {(2) (μ + 2) + μ (1) (μ + 2) + (μ + 2) (ν + 2) + ν (1) (ν + 2) \\ + (ν + 2) (2)} - \frac{1}{2} {(2) (2) + (2) (μ + ν + 2) + (μ + ν) (1) (μ + ν + 2) \\ + (μ + ν + 2) (2)} \\ = - \frac{1}{2} (μ ν) < 0 f o r ν \geq μ \geq 1 . \end{array}

\Rightarrow S K_{1} (A) < S K_{1} (M_{2} (A)) □

Lemma 9.

Let

M_{3} (A)

be a unicyclic connected graph as presented in Figure 3, where

d_{A} (ω_{i}, ω_{i + 1}) = d_{M_{3} (A)} (ω_{i}, ω_{i + 1}) \geq 2

. Then

S K_{1} (A) < S K_{1} (M_{3} (A)); v \geq μ \geq 1

Proof.

Following the previous lemma and by the definition of

S K_{1} (A)

, we find

\begin{array}{l} S K_{1} (A) - S K_{1} (M_{3} (A)) & = \frac{1}{2} [{d (ω_{i - 1}) . d (ω_{i})} + \sum_{k = 1}^{μ} {d (ω_{i, j}) . d (ω_{i})} + {d (ω_{i}) . d (ω_{i + 1})} \\ + {d (ω_{i + 1}) . d (ω_{j})} + \sum_{l = 1}^{ν} {d (ω_{j, ν}) . d (ω_{j})} + {d (ω_{j}) . d (ω_{j + 1})}] \\ - \frac{1}{2} [{d (ω_{i - 1}) . d (ω_{i})} + \sum_{k = 1}^{μ - 1} {d (ω_{i, μ - 1}) . d (ω_{i})} + {d (ω_{i}) . d (ω_{i + 1})} \\ + {d (ω_{i + 1}) . d (ω_{j})} + \sum_{l = 1}^{ν + 1} {d (ω_{j, ν}) . d (ω_{j})} + {d (ω_{j}) . d (ω_{j + 1})}] \\ = \frac{1}{2} [{d (ω_{i - 1}) . d (ω_{i})} + μ {d (ω_{i, j}) . d (ω_{i})} + {d (ω_{i}) . d (ω_{i + 1})} \\ + {d (ω_{i + 1}) . d (ω_{j})} + ν {d (ω_{j, ν}) . d (ω_{j})} + {d (ω_{j}) . d (ω_{j + 1})}] \\ - \frac{1}{2} [{d (ω_{i - 1}) . d (ω_{i})} + (μ - 1) {d (ω_{i, μ - 1}) . d (ω_{i})} + {d (ω_{i}) . d (ω_{i + 1})} \\ + {d (ω_{i + 1}) . d (ω_{j})} + (ν + 1) {d (ω_{j, ν}) . d (ω_{j})} + {d (ω_{j}) . d (ω_{j + 1})}] \\ = \frac{1}{2} {(2) (μ + 2) + μ (1) (μ + 2) + (μ + 2) (2) + (2) (ν + 2) \\ + ν (1) (ν + 2) + (ν + 2) (2)} - \frac{1}{2} {2 (μ - 1 + 2) + (μ - 1) (1) \\ (μ - 1 + 2) + (μ - 1 + 2) (2) + (2) (1 + ν + 2) + (ν + 1) (1) (ν + 1 + 2) \\ + (ν + 1 + 2) (2)} \\ = \frac{1}{2} (2 μ - 2 ν - 2) = μ - ν - 1 < 0 ν \geq μ \geq 1 \end{array}

\Rightarrow S K_{1} (A) < S K_{1} (M_{3} (A)) □

Hence, the proof is complete.

Lemma 10.

Let

M_{4} (A)

be the graph attained from

A

as illustrated in Figure 4. For any

ν \geq μ \geq 1

, we have

S K_{1} (A) < S K_{1} (M_{4} (A))

Proof.

d_{A} (ω_{i}, ω_{i + 1}) = 1

then

d_{M_{4} (A)} (ω_{i}) + d_{M_{4} (A)} (ω_{i + 1}) = μ + 2 + v + 2 = d_{A} (ω_{i}) + d_{A} (ω_{j})

and by the definition of

S K_{1} (A)

, we have

\begin{array}{l} S K_{1} (A) - S K_{1} (M_{4} (A)) & = \frac{1}{2} [{d (ω_{i - 1}) . d (ω_{i})} + \sum_{j = 1}^{μ} {d (ω_{i, j}) . d (ω_{i})} + {d (ω_{i}) . d (ω_{i + 1})} \\ + \sum_{k = 1}^{ν} {d (ω_{i + 1, k}) . d (ω_{i + 1})} + {d (ω_{i + 1}) . d (ω_{i + 2})}] - \frac{1}{2} [{d (ω_{i - 1}) \\ . d (ω_{i})} + \sum_{j = 1}^{μ - 1} {d (ω_{i, μ - 1}) . d (ω_{i})} + {d (ω_{i}) . d (ω_{i + 1})} \\ + \sum_{k = 1}^{ν + 1} {d (ω_{i + 1, k}) . d (ω_{i + 1})} + {d (ω_{i + 1}) . d (ω_{i + 2})}] \\ = \frac{1}{2} [{d (ω_{i - 1}) . d (ω_{i})} + μ {d (ω_{i, j}) . d (ω_{i})} + {d (ω_{i}) . d (ω_{i + 1})} \\ + ν {d (ω_{i + 1, k}) . d (ω_{i + 1})} + {d (ω_{i + 1}) . d (ω_{i + 2})}] - \frac{1}{2} [{d (ω_{i - 1}) \\ . d (ω_{i})} + (μ - 1) {d (ω_{i, μ - 1}) . d (ω_{i})} + {d (ω_{i}) . d (ω_{i + 1})} \\ + (ν + 1) {d (ω_{i + 1, k}) . d (ω_{i + 1})} + {d (ω_{i + 1}) . d (ω_{i + 2})}] \\ = \frac{1}{2} {(2) (μ + 2) + μ (1) (μ + 2) + (μ + 2) (ν + 2) + ν (1) (ν + 2) \\ + (ν + 2) (2)} - \frac{1}{2} {(2) (μ - 1 + 2) + (μ - 1) (1) (μ - 1 + 2) \\ + (μ - 1 + 2) (ν + 1 + 2) + (ν + 1) (1) (ν + 1 + 2) + (ν + 1 + 2) (2)} \\ = \frac{1}{2} (μ - ν - 1) < 0 f o r ν \geq μ \geq 1 . \end{array}

\Rightarrow S K_{1} (A) < S K_{1} (M_{4} (A)) □

Now first, we find the extremal graphs having the greatest value and then give an ordering of the unicyclic connected graphs in decreasing order for the

S K_{1}

index.

Theorem 4

Ref. [19]. Let

X (r, 3; a, b, c)

;

a + b + c = r - 3

;

a \geq b \geq c \geq 1

be a set of unicyclic connected graphs with

r \geq 5

. Then the first maximum and second maximum values of the

S K_{1}

index are attained by

X (r, 3; r - 3,0, 0)

and

X (r, 3; r - 4,1, 0)

, respectively, i.e.,

S K_{1} (X (r, 3; r - 4,1, 0)) < S K_{1} (X (r, 3; r - 3,0, 0))

(See Figure 7.)

Proof.

We need only to prove

S K_{1} (X (r, 3; a, b, c)) < S K_{1} (X (r, 3; a + 1, b - 1, c))

Consider

\begin{array}{l} S K_{1} (X (r, 3; a, b, c)) - S K_{1} (X (r, 3; a + 1, b - 1, c)) \\ = \frac{1}{2} {a (1) (a + 2) + (a + 2) (b + 2) + b (1) (b + 2) + (b + 2) (c + 2) + c (1) (c + 2) \\ + (c + 2) (a + 2)} - \frac{1}{2} {(a + 1) (1) (a + 1 + 2) + (a + 1 + 2) (b - 1 + 2) \\ + (b - 1) (1) (b - 1 + 2) + (b - 1 + 2) (c + 2) + c (1) (c + 2) + (c + 2) (a + 1 + 2)} \\ = \frac{1}{2} (- a + b - 1) < 0 f o r a \geq b \geq c \geq 1 . \end{array} □

Hence, the result follows.

Lemma 11.

Ref. [19] If

S K_{1} (U_{r} (μ))

is the maximum for fixed

r \geq 5

, where

1 \leq μ \leq r - 4

, then we have

μ = 1

r - 4

Proof.

For

r = 5

μ = 1 = r - 4

and there is only one graph

U_{5} (1)

. So, there cannot be a debate in choosing the maximum or the minimum.

Suppose that

3 \leq μ \leq r - 5

\begin{array}{l} S K_{1} (U_{r} (μ)) & = \frac{1}{2} {2 (2) (r - μ - 4 + 3) + (r - μ - 4) (1) (r - μ - 4 + 3) + (r - μ - 4 + 3) \\ (μ + 1) + μ (1) (μ + 1) + (2) (2)} = \frac{1}{2} (r^{2} + μ^{2} - r μ + 3) \end{array}

\begin{array}{l} S K_{1} (U_{r} (μ + 1)) = \frac{1}{2} (r^{2} + μ^{2} + 3 r - r μ + 6) \end{array}

By using the above calculations, we determine

S K_{1} (U_{r} (μ + 1)) - S K_{1} (U_{r} (μ)) = \frac{3}{2} (r + 1) > 0

\Rightarrow S K_{1} (U_{r} (μ + 1)) > S K_{1} (U_{r} (μ))

concluding that

S K_{1} (U_{r} (μ)) > S K_{1} (U_{r} (r - 4))

where

S K_{1} (U_{r} (r - 4)) = \frac{1}{2} (r^{2} - 4 r + 19)

For

p = 1,2

, we have

\begin{array}{l} S K_{1} (U_{r} (1)) = \frac{1}{2} (r^{2} - r + 4) \end{array}

\begin{array}{l} S K_{1} (U_{r} (2)) = \frac{1}{2} (r^{2} - 2 r + 7) \end{array}

Furthermore

S K_{1} (U_{r} (1)) - S K_{1} (U_{r} (2)) = \frac{1}{2} (r - 3) > 0

S K_{1} (U_{r} (1)) - S K_{1} (U_{r} (r - 4)) = \frac{3}{2} (r - 5) > 0

S K_{1} (U_{r} (2)) - S K_{1} (U_{r} (r - 4)) = r - 6 > 0

By the above inequalities, we have

S K_{1} (U_{r} (1)) > S K_{1} (U_{r} (2)) > S K_{1} (U_{r} (μ)) > S K_{1} (U_{r} (r - 4)), U_{r} (μ); 3 \leq μ \leq r - 5

The above used graphs are shown in Figure 8. Therefore,

U_{r} (1)

is a graph with the first maximum and

U_{r} (2)

with the second maximum

S K_{1}

index, and we are complete. □

Theorem 5.

Let

A

having girth

g

with

4 \leq g \leq r

, be a connected unicyclic graph. Then

S K_{1} (A) \leq S K_{1} (X_{r, g})

where

X_{r, g} = X (r, g; r - g, 0, \dots, 0)

Proof.

Let

A \in O_{r, g}

, where

O_{r, g}

be the set of unlabelled connected unicyclic graphs having order

r

and girth

g

with

r \geq g > 3

. If

g = r

, then

A = C_{g}

; for

g = r - 1

then

A = X (r, r - 1; 1,0, \dots, 0)

. Suppose that

3 \leq g \leq r - 2

and

A

has the largest

S K_{1}

index.

A

is a graph with some vertex disjoint trees having each a common vertex with

C_{g}

. After applying

M_{1}

-transformation, the trees are reduced to some stars with centers on

C_{g}

and the

S K_{1}

index strictly increases by Lemma 7. Since

S K_{1} (A)

is the maximum, it implies that

A = X (r, g; r_{1}, \dots, r_{g})

where

r_{1}, \dots, r_{g} \geq 0

and

r_{1} + \dots + r_{g} = r - g

. All the pendant edges attached at the vertices of

C_{g}

are made incident to the unique and same vertex. After applying

M_{2}, M_{3}

-transformations several times, that would give

A = X_{r, g} = X (r, g; r - g, 0, \dots, 0)

. □

Remark 2.

r - 1 \geq g \geq 3

then

S K_{1} (X (r, g; r - g, 0, \dots, 0)) > S K_{1} (X (r, g + 1; r - g - 1,0, \dots, 0))

by Case 1 of Lemma 7.

Lemma 12.

(1) For

p = r - g \geq 3

, we have

S K_{1} (A_{2}) < S K_{1} (A_{1})

(2) For

p = r - g \geq 2

, we have

(a): $S K_{1} (A_{3}) < S K_{1} (A_{1})$ .
(b): $S K_{1} (A_{4}) < S K_{1} (A_{1})$ .
(c): $S K_{1} (A_{5}) < S K_{1} (A_{1})$ .

See Figure 6.

Proof.

\begin{array}{l} S K_{1} (A_{2}) - S K_{1} (A_{1}) \\ = \frac{1}{2} {(2) (μ - 2 + 2) + (μ - 2) (1) (μ - 2 + 2) + (μ - 2 + 2) (2) + (2) (4) + (4) (2) + (4) (2)} \\ - \frac{1}{2} {(2) (μ - 1 + 2) + (μ - 1) (1) (μ - 1 + 2) + (μ - 1 + 2) (3) + (3) (1) + (3) (2) + (2) (2)} \\ = \frac{1}{2} (- 3 μ + 7) < 0 . \end{array}

\begin{array}{l} (a) S K_{1} (A_{3}) - S K_{1} (A_{1}) \\ = \frac{1}{2} {(μ - 1) (1) (μ - 1 + 2) + (μ - 1 + 2) (2) + (2) (3) + (3) (1) + (3) (2)} \\ - \frac{1}{2} {(μ - 1) (1) (μ - 1 + 2) + (μ - 1 + 2) (3) + (3) (1) + (3) (2) + (2) (2)} \\ = \frac{1}{2} (- μ + 1) < 0 . \end{array}

\begin{array}{l} (b) S K_{1} (A_{4}) - S K_{1} (A_{1}) \\ = \frac{1}{2} {(2 + μ - 1) (2) + (μ - 2) (1) (μ - 2 + 3) + (μ - 2 + 3) (2) + (2) (1) + (μ - 1 + 2) (2) \\ + (2) (2)} - \frac{1}{2} {(2 + μ - 1) (2) + (μ - 1) (1) (μ - 1 + 2) + (μ - 1 + 2) (3) + (3) (1) + (3) (2)} \\ = - \frac{3}{2} < 0 . \end{array}

\begin{array}{l} (c) S K_{1} (A_{5}) - S K_{1} (A_{1}) \\ = \frac{1}{2} {(2) (3) + (3) (μ - 1 + 1) + (μ - 1) (1) (μ - 1 + 1) + (3) (2) + (2) (2)} \\ - \frac{1}{2} {(2) (μ - 1 + 2) + (μ - 1) (1) (μ - 1 + 2) + (μ - 1 + 2) (3) + (3) (1) + (3) (2)} \\ = \frac{1}{2} (- 3 μ + 3) < 0 . \end{array} □

Theorem 6.

(a) Let

A \in O_{r, g} \ {X_{r, g}}

, where

r \geq 6, (4 \leq g \leq r - 2)

. Then

A

has a maximum

S K_{1}

index if, and only if,

A = A_{1}

(b) Let

A \in O_{r, g} \ {(A_{1} \cup X_{r, g})}

, where

r \geq 7, (4 \leq g \leq r - 3)

. Then

A

has a maximum

S K_{1}

index if, and only if,

A = X (r, g; r - g - 1,0, 1,0, \dots, 0) = A_{3}

Proof.

Let

A \in O_{r, g}

be a connected unicyclic graph having the second or third maximum

S K_{1}

index. Suppose that there is a vertex with a degree of at least 3 in a cycle

C_{g}

A

. Since

A \neq X_{r, g}

, then there is at least one non-pendant vertex in

C

Case 1: When there is exactly one non-pendant vertex outside

C,

we obtained

A

by attaching the

μ

pendant edges to a pendant vertex of

X (r - μ, g; r - g - μ, 0, \dots, 0)

where

(1 \leq μ \leq r - g - 1)

Lemma 11 states that for

μ = 1

r - 4

we have the maximum of

S K_{1} (U_{r} (μ))

with corresponding graphs

A_{4}

and

A_{5}

However, Lemma 12 implies that the graphs with the second or third maximum

S K_{1}

index, cannot be

A_{4}

A_{5}

Case 2: When there are at least two non-pendant vertices outside

C

, after the continuous application of

M_{1}

-transformation, we have

S K_{1} (A) < m a x {S K_{1} (A_{4}), S K_{1} (A_{5})} < S K_{1} (A_{3}) < S K_{1} (A_{1}) < S K_{1} (X_{r, g})

\begin{matrix} as S K_{1} (A_{1}) - S K_{1} (X_{r, g}) = {\frac{1}{2} (r^{2} + g^{2} + 5 r - g - 2 r g + 1)} - {\frac{1}{2} (r^{2} + g^{2} + \\ 6 r - 2 g - 2 r g)} = \frac{1}{2} (- r + g + 1) < 0 \end{matrix}

Thus, we knew that if

A

has a second or third maximum

S K_{1}

index then the two vertices on

C_{g}

must exist having a degree of at least three.

(a) For

A \neq X_{r, g}

, if

A

has a maximum

S K_{1}

then

C_{g}

cannot have three vertices with a degree of at least 3.

We obtained

X_{r, g}

after several applications of

M_{i}

-transformations

(i \geq 1)

. However, we found a graph with an index less than

X_{r, g}

, we see that

S K_{1} (A) < m a x {S K_{1} (A_{3}), S K_{1} (A_{1})} = S K_{1} (A_{1}) < S K_{1} (X_{r, g})

It implies that

A

has exactly two vertices

m, n

C_{g}

having a degree of at least 3.

Degrees of

m

and

n

must be as:

d (m) = r - g + 1, d (n) = 3

, since other cases cannot hold because if

d (m) = 2

then

A

becomes

X_{r, g}

(since our supposition of degree is at least

3

) and if

d (m) = 4

then

A

cannot become the second maximum because

A

with

d (m) = 3

has a greater index than

A

with

d (m) = 4

Now, if

d (m, n) = 1

then

A = A_{1}

and if

d (m, n) \geq 2

then

A \in Y (r, g)

class including

A_{3}

Lemma 12 implies that, in this case, the extremal graph is

A_{1}

(b) For

A \in O_{r, g} \ (A_{1} \cup X_{r, g})

, by the same argument we deduce that

C_{g}

cannot have three vertices with a degree of at least 3, if

A

has a maximum

{S K}_{1}

index, since, in this case, we would have

S K_{1} (A) < S K_{1} (A_{3}) < S K_{1} (A_{1}) < S K_{1} (X_{r, g})

\begin{matrix} as S K_{1} (A_{3}) - S K_{1} (A_{1}) = {\frac{1}{2} (r^{2} + g^{2} + 4 r - 2 r g + 2)} - {\frac{1}{2} (r^{2} + g^{2} + 5 r - \\ g - 2 r g + 1)} = \frac{1}{2} (- r + g + 2) < 0 \end{matrix}

It implies that

A

has exactly two vertices

a, b

C_{g}

having a degree of at least 3. By the same argument (used above),

d (m) = r - g

and

d (n) = 4

d (m, n) = 1

then

A = A_{6}

and if

d (m, n) \geq 2

then

A \in Z (r, g)

class including

A_{2}

, which ends the proof. □

(See Figure 10.)

4. Ordering Unicyclic Structures with the Greatest SK₂ Index

In this section, we use graph transformations which increase the

S K_{2}

index.

Lemma 13.

Let

M_{1} (A)

be a unicyclic connected graph as shown in Figure 1, then

S K_{2} (A) < S K_{2} (M_{1} (A))

for any

μ, v \geq 0

Proof.

Case 1: Ref. [19] When

M_{1}

is performed excluding the vertices of

C_{g}

\begin{array}{l} S K_{2} (A) - S K_{2} (M_{1} (A)) & = \frac{1}{4} \sum_{x y \in E (A) \ {y z}} [(d_{x} + d_{y})^{2} - (d_{x} + d_{y} + d_{z} - 1)^{2}] \\ + \frac{1}{4} \sum_{x z \in E (A) \ {y z}} [(d_{x} + d_{z})^{2} - (d_{x} + d_{y} + d_{z} - 1)^{2}] < 0; a s d_{y} \geq 2 \end{array}

Case 2: When

M_{1}

is performed on the vertices of

C_{g}

We have

d_{A} (ω_{i}) = d_{M_{1} (A)} (ω_{i}) - v - 1 < d_{M_{1} (A)} (ω_{i})

and

d_{M_{1} (A)} (ω_{i}) + d_{M_{1} (A)} (ω_{i + 1}) = μ + v + 4

Therefore, for

j = \bar{1, μ} = 1,2, \dots, μ

k = \bar{1, v} = 1,2, \dots, v

and by the definition of the

S K_{2}

index, we find

\begin{array}{l} S K_{2} (A) - S K_{2} (M_{1} (A)) & = \frac{1}{4} [{d (ω_{i - 1}) + d (ω_{i})}^{2} + μ {d (ω_{i, j}) + d (ω_{i})}^{2} + {d (ω_{i}) \\ + d (ω_{i + 1})}^{2} + ν {d (ω_{i + 1, k}) + d (ω_{i + 1})}^{2} + {d (ω_{i + 1}) + d (ω_{i + 2})}^{2}] \\ - \frac{1}{4} [{d (ω_{i - 1}) + d (ω_{i})}^{2} + (μ + ν + 1) {d (ω_{i, j}) + d (ω_{i})}^{2} \\ + {d (ω_{i}) + d (ω_{i + 2})}^{2}] \\ = \frac{1}{4} {(2 + μ + 2)^{2} + μ (1 + μ + 2)^{2} + (μ + 2 + ν + 2)^{2} + ν (1 + ν + 2)^{2} \\ + (ν + 2 + 2)^{2}} - \frac{1}{4} {(2 + μ + ν + 1 + 2)^{2} + (μ + ν + 1) \\ (1 + μ + ν + 1 + 2)^{2} + (μ + ν + 1 + 2 + 2)^{2}} \\ = - \frac{1}{4} (3 μ^{2} + 3 ν^{2} + 19 μ + 19 ν + 20 μ ν + 3 μ^{2} ν + 3 μ ν^{2} + 18) < 0 . \end{array}

\Rightarrow S K_{2} (A) < S K_{2} (M_{1} (A)) □

Lemma 14.

Let

M_{2} (A)

be a unicyclic connected graph as depicted in Figure 2, where

d_{A} (ω_{i}, ω_{i + 1}) = 1

. Then

S K_{2} (A) < S K_{2} (M_{2} (A))

for any

v \geq μ \geq 1

Proof.

Since

d_{M_{2} (A)} (ω_{i}) = 2 < d_{A} (ω_{i}) = μ + 2

and

d_{A} (ω_{i + 1}) = ν + 2 < d_{M_{2} (A)} (ω_{i + 1}) = ν + μ + 2

\begin{array}{l} S K_{2} (A) - S K_{2} (M_{2} (A)) & = \frac{1}{4} [{d (ω_{i - 1}) + d (ω_{i})}^{2} + \sum_{j = 1}^{μ} {d (ω_{i, j}) + d (ω_{i})}^{2} + {d (ω_{i}) \\ + d (ω_{i + 1})}^{2} + \sum_{k = 1}^{ν} {d (ω_{i + 1, k}) + d (ω_{i + 1})}^{2} + {d (ω_{i + 1}) + d (ω_{i + 2})}^{2}] \\ - \frac{1}{4} [{d (ω_{i - 1}) + d (ω_{i})}^{2} + {d (ω_{i}) + d (ω_{i + 1})}^{2} \\ + (μ + ν) {d (ω_{i, j}) + d (ω_{i + 1})}^{2} + {d (ω_{i + 1}) + d (ω_{i + 2})}^{2}] \\ = \frac{1}{4} [{d (ω_{i - 1}) + d (ω_{i})}^{2} + μ {d (ω_{i, j}) + d (ω_{i})}^{2} + {d (ω_{i}) \\ + d (ω_{i + 1})}^{2} + ν {d (ω_{i + 1, k}) + d (ω_{i + 1})}^{2} + {d (ω_{i + 1}) + d (ω_{i + 2})}^{2}] \\ - \frac{1}{4} [{d (ω_{i - 1}) + d (ω_{i})}^{2} + {d (ω_{i}) + d (ω_{i + 1})}^{2} \\ + (μ + ν) {d (ω_{i, j}) + d (ω_{i + 1})}^{2} + {d (ω_{i + 1}) + d (ω_{i + 2})}^{2}] \\ = \frac{1}{4} {(2 + μ + 2)^{2} + μ (1 + μ + 2)^{2} + (μ + 2 + ν + 2)^{2} + ν \\ (1 + ν + 2)^{2} + (ν + 2 + 2)^{2}} - \frac{1}{4} {(2 + 2)^{2} + (2 + μ + ν + 2)^{2} \\ + (μ + ν) (1 + μ + ν + 2)^{2} + (μ + ν + 2 + 2)^{2}} \\ = - \frac{μ ν}{4} (3 μ + 3 ν + 14) < 0 f o r ν \geq μ \geq 1 . \end{array}

\Rightarrow S K_{2} (A) < S K_{2} (M_{2} (A)) □

Lemma 15.

Let

M_{3} (A)

be a unicyclic connected graph as presented in Figure 3, where

d_{A} (ω_{i}, ω_{i + 1}) = d_{M_{3} (A)} (ω_{i}, ω_{i + 1}) \geq 2

. Then

S K_{2} (A) < S K_{2} (M_{3} (A)); v \geq μ \geq 1

Proof.

Following the previous lemma and by the definition of

S K_{2} (A)

, we find

\begin{array}{l} S K_{2} (A) - S K_{2} (M_{3} (A)) & = \frac{1}{4} [{d (ω_{i - 1}) + d (ω_{i})}^{2} + \sum_{k = 1}^{μ} {d (ω_{i, j}) + d (ω_{i})}^{2} \\ + {d (ω_{i}) + d (ω_{i + 1})}^{2} + {d (ω_{i + 1}) + d (ω_{j})}^{2} + \sum_{l = 1}^{ν} {d (ω_{j, ν}) + d (ω_{j})}^{2} \\ + {d (ω_{j}) + d (ω_{j + 1})}^{2}] - \frac{1}{4} [{d (ω_{i - 1}) + d (ω_{i})}^{2} + \sum_{k = 1}^{μ - 1} \\ {d (ω_{i, μ - 1}) + d (ω_{i})}^{2} + {d (ω_{i}) + d (ω_{i + 1})}^{2} + {d (ω_{i + 1}) \\ + d (ω_{j})}^{2} + \sum_{l = 1}^{ν + 1} {d (ω_{j, ν}) + d (ω_{j})}^{2} + {d (ω_{j}) + d (ω_{j + 1})}^{2}] \\ = \frac{1}{4} [{d (ω_{i - 1}) + d (ω_{i})}^{2} + μ {d (ω_{i, j}) + d (ω_{i})}^{2} \\ + {d (ω_{i}) + d (ω_{i + 1})}^{2} + {d (ω_{i + 1}) + d (ω_{j})}^{2} + ν {d (ω_{j, ν}) + d (ω_{j})}^{2} \\ + {d (ω_{j}) + d (ω_{j + 1})}^{2}] - \frac{1}{4} [{d (ω_{i - 1}) + d (ω_{i})}^{2} + (μ - 1) \\ {d (ω_{i, μ - 1}) + d (ω_{i})}^{2} + {d (ω_{i}) + d (ω_{i + 1})}^{2} + {d (ω_{i + 1}) \\ + d (ω_{j})}^{2} + (ν + 1) {d (ω_{j, ν}) + d (ω_{j})}^{2} + {d (ω_{j}) + d (ω_{j + 1})}^{2}] \\ = \frac{1}{4} {(2 + μ + 2)^{2} + μ (1 + μ + 2)^{2} + (μ + 2 + 2)^{2} + (2 + ν + 2)^{2} \\ + ν (1 + ν + 2)^{2} + (ν + 2 + 2)^{2}} - \frac{1}{4} {(2 + μ - 1 + 2)^{2} \\ + (μ - 1) (1 + μ - 1 + 2)^{2} + (μ - 1 + 2 + 2)^{2} + (2 + 1 + ν + 2)^{2} \\ + (ν + 1) (1 + ν + 1 + 2)^{2} + (ν + 1 + 2 + 2)^{2}} \\ = \frac{1}{4} [(μ - ν) {3 μ + 3 ν + 13} - 6 ν - 7] < 0 ν \geq μ \geq 1 . \end{array}

\Rightarrow S K_{2} (A) < S K_{2} (M_{3} (A)) □

Hence, the proof is complete.

Lemma 16.

Let

M_{4} (A)

be the graph as illustrated in Figure 4. For any

ν \geq μ \geq 1

, we have

S K_{2} (A) < S K_{2} (M_{4} (A))

Proof.

d_{A} (ω_{i}, ω_{i + 1}) = 1

then

d_{M_{4} (A)} (ω_{i}) + d_{M_{4} (A)} (ω_{i + 1}) = μ + 2 + v + 2 = d_{A} (ω_{i}) + d_{A} (ω_{j})

and by the definition of

S K_{2} (A)

, we have

\begin{array}{l} S K_{2} (A) - S K_{2} (M_{4} (A)) & = \frac{1}{4} [{d (ω_{i - 1}) + d (ω_{i})}^{2} + \sum_{j = 1}^{μ} {d (ω_{i, j}) + d (ω_{i})}^{2} + {d (ω_{i}) \\ + d (ω_{i + 1})}^{2} + \sum_{k = 1}^{ν} {d (ω_{i + 1, k}) + d (ω_{i + 1})}^{2} + {d (ω_{i + 1}) + d (ω_{i + 2})}^{2}] \\ - \frac{1}{4} [{d (ω_{i - 1}) + d (ω_{i})}^{2} + \sum_{j = 1}^{μ - 1} {d (ω_{i, μ - 1}) + d (ω_{i})}^{2} + {d (ω_{i}) \\ + d (ω_{i + 1})}^{2} + \sum_{k = 1}^{ν + 1} {d (ω_{i + 1, k}) + d (ω_{i + 1})}^{2} + {d (ω_{i + 1}) + d (ω_{i + 2})}^{2}] \\ = \frac{1}{4} [{d (ω_{i - 1}) + d (ω_{i})}^{2} + μ {d (ω_{i, j}) + d (ω_{i})}^{2} + {d (ω_{i}) \\ + d (ω_{i + 1})}^{2} + ν {d (ω_{i + 1, k}) + d (ω_{i + 1})}^{2} + {d (ω_{i + 1}) + d (ω_{i + 2})}^{2}] \\ - \frac{1}{4} [{d (ω_{i - 1}) + d (ω_{i})}^{2} + (μ - 1) {d (ω_{i, μ - 1}) + d (ω_{i})}^{2} + {d (ω_{i}) \\ + d (ω_{i + 1})}^{2} + (ν + 1) {d (ω_{i + 1, k}) + d (ω_{i + 1})}^{2} + {d (ω_{i + 1}) + d (ω_{i + 2})}^{2}] \\ = \frac{1}{4} {(2 + μ + 2)^{2} + μ (1 + μ + 2)^{2} + (μ + 2 + ν + 2)^{2} + ν \\ (1 + ν + 2)^{2} + (ν + 2 + 2)^{2}} - \frac{1}{4} {(2 + μ - 1 + 2)^{2} + (μ - 1) \\ (1 + μ - 1 + 2)^{2} + (μ - 1 + 2 + ν + 1 + 2)^{2} + (ν + 1) \\ (1 + ν + 1 + 2)^{2} + (ν + 1 + 2 + 2)^{2}} \\ = \frac{1}{4} [(μ - ν) {3 (μ + ν) + 11} - 6 ν - 14] < 0 f o r ν \geq μ \geq 1 . \end{array}

\Rightarrow S K_{2} (A) < S K_{2} (M_{4} (A)) □

Now first, we find the extremal graphs having the greatest value and then give an ordering of the unicyclic connected graphs in decreasing order for the

S K_{2}

index.

Theorem 7.

Ref. [19] Let

X (r, 3; a, b, c)

;

a + b + c = r - 3

;

a \geq b \geq c \geq 1

be a set of unicyclic connected graphs with

r \geq 5

. Then the first maximum and second maximum values of the

S K_{2}

index are attained by

X (r, 3; r - 3,0, 0)

and

X (r, 3; r - 4,1, 0),

respectively,

i . e .

S K_{2} (X (r, 3; r - 4,1, 0)) < S K_{2} (X (r, 3; r - 3,0, 0))

See Figure 10.

Proof.

We need only to prove

S K_{2} (X (r, 3; a, b, c)) < S K_{2} (X (r, 3; a + 1, b - 1, c))

\begin{array}{l} S K_{2} (X (r, 3; a, b, c)) - S K (X_{2} (r, 3; a + 1, b - 1, c)) \\ = \frac{1}{4} {a (1 + a + 2)^{2} + (a + 2 + b + 2)^{2} + b (1 + b + 2)^{2} + (b + 2 + c + 2)^{2} + c (1 + c + 2)^{2} \\ + (c + 2 + a + 2)^{2}} - \frac{1}{4} {(a + 1) (1 + a + 1 + 2)^{2} + (a + 1 + 2 + b - 1 + 2)^{2} \\ + (b - 1) (1 + b - 1 + 2)^{2} + (b - 1 + 2 + c + 2)^{2} + c (1 + c + 2)^{2} + (c + 2 + a + 1 + 2)^{2}} \\ = \frac{1}{4} (- 3 a^{2} + 3 b^{2} - 17 a + 11 b - 14) < 0 f o r a \geq b \geq c \geq 1 . \end{array} □

Hence, the result follows.

Lemma 17.

Ref. [19] If

S K_{2} (U_{r} (μ))

is the maximum for fixed

r \geq 5

, where

1 \leq μ \leq r - 4

, then we have

μ = 1

r - 4

Proof.

For

r = 5

μ = 1 = r - 4

and there is only one graph

U_{5} (1)

. Therefore, there cannot be a debate in choosing the maximum or minimum.

Suppose that

3 \leq μ \leq r - 5

, then

\begin{array}{l} S K_{2} (U_{r} (μ)) & = \frac{1}{4} {2 (2 + r - μ - 4 + 3)^{2} + (r - μ - 4) (1 + r - μ - 4 + 3)^{2} \\ + (r - μ - 4 + 3 + μ + 1)^{2} + μ (1 + μ + 1)^{2} + (2 + 2)^{2}} \\ = \frac{1}{4} (r^{3} - r^{2} + 2 μ^{2} - 3 r^{2} μ + 3 r μ^{2} + 4 r + 4 r μ + 18) \end{array}

\begin{array}{l} S K_{2} (U_{r} (μ + 1)) = \frac{1}{4} (r^{3} + 2 r^{2} + 8 μ^{2} - 3 r^{2} μ + 3 r μ^{2} + 7 r + 12 μ - 2 r μ + 34) \end{array}

By using the above calculations, we determine

S K_{2} (U_{r} (μ + 1)) - S K_{2} (U_{r} (μ)) = \frac{1}{4} (3 r^{2} + 6 μ^{2} + 3 r + 12 μ - 6 r μ + 16) > 0

\Rightarrow S K_{2} (U_{r} (μ + 1)) > S K_{2} (U_{r} (μ))

concluding that

S K_{2} (U_{r} (μ)) > S K_{2} (U_{r} (r - 4))

where

\begin{array}{l} S K_{2} (U_{r} (r - 4)) & = \frac{1}{4} {2 (2 + 3)^{2} + (3 + r - 4 + 1)^{2} + (r - 4) (1 + r - 4 + 1)^{2} + (2 + 2)^{2}} \\ = \frac{1}{4} (r^{3} - 7 r^{2} + 20 r + 50) \end{array}

For

μ = 1,2

, we have

\begin{array}{l} S K_{2} (U_{r} (1)) = \frac{1}{4} (r^{3} - 4 r^{2} + 11 r + 20) \end{array}

\begin{array}{l} S K_{2} (U_{r} (2)) = \frac{1}{4} (r^{3} - 7 r^{2} + 24 r + 26) \end{array}

Furthermore

S K_{2} (U_{r} (1)) - S K_{2} (U_{r} (2)) = \frac{1}{4} (3 r^{2} - 13 r - 6) > 0

S K_{2} (U_{r} (1)) - S K_{2} (U_{r} (r - 4)) = \frac{1}{4} (3 r^{2} - 9 r - 30) > 0

S K_{2} (U_{r} (2)) - S K_{2} (U_{r} (r - 4)) = r - 6 > 0

By the above inequalities, we have

S K_{2} (U_{r} (1)) > S K_{2} (U_{r} (2)) > S K_{2} (U_{r} (μ)) > S K_{2} (U_{r} (r - 4)), U_{r} (μ); 3 \leq μ \leq r - 5 □

The above used graphs are shown in Figure 8. Therefore,

U_{r} (1)

is a graph with the first maximum and

U_{r} (2)

with the second maximum

S K_{2}

index, andwe are complete.

Theorem 8.

Let

A

having girth

g

with

4 \leq g \leq r

, be a connected unicyclic graph. Then

\begin{array}{l} S K_{2} (A) \leq S K_{2} (X_{r, g}) \end{array}

where

X_{r, g} = X (r, g; r - g, 0, \dots, 0)

Proof.

Let

A \in O_{r, g}

, where

O_{r, g}

be the set of unlabelled connected unicyclic graphs having order

r

and girth

g

with

r \geq g > 3

. If

g = r

, then

A = C_{g}

; for

g = r - 1

then

A = X (r, r - 1; 1,0, \dots, 0)

. Suppose that

3 \leq g \leq r - 2

and

A

has the largest

S K_{2}

index.

A

is a graph with some vertex disjoint trees having each a common vertex with

C_{g}

. After applying

M_{1}

-transformation, the trees are reduced to some stars with centers on

C_{g}

and the

S K_{2}

index strictly increases by Lemma 13. Since

S K_{2} (A)

is the maximum, it implies that

A = X (r, g; r_{1}, \dots, r_{g})

where

r_{1}, \dots, r_{g} \geq 0

and

r_{1} + \dots + r_{g} = r - g

. All the pendant edges attached at the vertices of

C_{g}

are made incident to the unique and same vertex. After applying the

M_{2}, M_{3}

-transformations several times, that would give

A = X_{r, g} = X (r, g; r - g, 0, \dots, 0)

. □

Remark 3.

r - 1 \geq g \geq 3

then

S K_{2} (X (r, g; r - g, 0, \dots, 0)) > S K_{2} (X (r, g + 1; r - g - 1,0, \dots, 0))

by Case 1 of Lemma 13.

Lemma 18.

For

p = r - g \geq 2

, we have

(a): $S K_{2} (A_{2}) < S K_{2} (A_{1})$ .
(b): $S K_{2} (A_{3}) < S K_{2} (A_{1})$ .
(c): $S K_{2} (A_{4}) < S K_{2} (A_{1})$ .
(d): $S K_{2} (A_{5}) < S K_{2} (A_{1})$ .

See Figure 6.

Proof.

\begin{array}{l} (a) S K_{2} (A_{2}) - S K_{2} (A_{1}) \\ = \frac{1}{4} {(2 + μ - 2 + 2)^{2} + (μ - 2) (1 + μ - 2 + 2)^{2} + (μ - 2 + 2 + 2)^{2} + (2 + 4)^{2} + (4 + 2)^{2} \\ + (4 + 2)^{2}} - \frac{1}{4} {(2 + μ - 1 + 2)^{2} + (μ - 1) (1 + μ - 1 + 2)^{2} + (μ - 1 + 2 + 3)^{2} + (3 + 1)^{2} \\ + (3 + 2)^{2} + (2 + 2)^{2}} \\ = - \frac{3}{4} {μ (μ + 3) - 12} < 0 . \end{array}

\begin{array}{l} (b) S K_{2} (A_{3}) - S K_{2} (A_{1}) \\ = \frac{1}{4} {(μ - 1) (1 + μ - 1 + 2)^{2} + (μ - 1 + 2 + 2)^{2} + (2 + 3)^{2} + (3 + 1)^{2} + (3 + 2)^{2}} \\ - \frac{1}{4} {(μ - 1) (1 + μ - 1 + 2)^{2} + (μ - 1 + 2 + 3)^{2} + (3 + 1)^{2} + (3 + 2)^{2} + (2 + 2)^{2}} \\ = \frac{1}{2} (- μ + 1) < 0 . \end{array}

\begin{array}{l} (c) S K_{2} (A_{4}) - S K_{2} (A_{1}) \\ = \frac{1}{4} {(2 + μ - 1 + 2)^{2} + (μ - 2) (1 + μ - 2 + 3)^{2} + (μ - 2 + 3 + 2)^{2} + (2 + 1)^{2} \\ + (μ - 1 + 2 + 2)^{2} + (2 + 2)^{2}} - \frac{1}{4} {(2 + μ - 1 + 2)^{2} + (μ - 1) (1 + μ - 1 + 2)^{2} \\ + (μ - 1 + 2 + 3)^{2} + (3 + 1)^{2} + (3 + 2)^{2}} \\ = - \frac{9}{2} < 0 . \end{array}

\begin{array}{l} (d) S K_{2} (A_{5}) - S K_{2} (A_{1}) \\ = \frac{1}{4} {(2 + 3)^{2} + (3 + μ - 1 + 1)^{2} + (μ - 1) (1 + μ - 1 + 1)^{2} + (3 + 2)^{2} + (2 + 2)^{2}} \\ - \frac{1}{4} {(2 + μ - 1 + 2)^{2} + (μ - 1) (1 + μ - 1 + 2)^{2} + (μ - 1 + 2 + 3)^{2} + (3 + 1)^{2} + (3 + 2)^{2}} \\ = - \frac{3}{4} {(μ - 1) (μ + 4)} < 0 . \end{array} □

Theorem 9.

(a) Let

A \in O_{r, g} \ {X_{r, g}}

, where

r \geq 4, (4 \leq g \leq r)

. Then

A

has a maximum

S K_{2}

index if, and only if,

A = A_{1}

(b) Let

A \in O_{r, g} \ {(A_{1} \cup X_{r, g})}

, where

r \geq 4, (4 \leq g \leq r)

. Then

A

has a maximum

S K_{2}

index if, and only if,

A = X (r, g; r - g - 1,0, 1,0, \dots, 0) = A_{3}

Proof.

Let

A \in O_{r, g}

be a connected unicyclic graph having a second or third maximum

S K_{2}

index. Suppose that there is a vertex with a degree at of least 3 in a cycle

C_{g}

A

. Since

A \neq X_{r, g}

, then there is at least one non-pendant vertex in

C

Case 1: When there is exactly one non-pendant vertex outside

C

, we obtained

A

by attaching the

μ

pendant edges to a pendant vertex of

X (r - μ, g; r - g - μ, 0, \dots, 0)

where

(1 \leq μ \leq r - g - 1)

Lemma 17 states that for

μ = 1

r - 4

we have a maximum of

S K_{2} (U_{r} (μ))

with corresponding graphs

A_{4}

and

A_{5}

, respectively.

However, Lemma 17 implies that the graphs with a second or third maximum

S K_{2}

index, cannot be

A_{4}

A_{5}

Case 2: When there are at least two non-pendant vertices outside

C,

after the continuous application of

M_{1}

-transformation, we have

S K_{2} (A) < m a x {S K_{2} (A_{4}), S K_{2} (A_{5})} < S K_{2} (A_{3}) < S K_{2} (A_{1}) < S K_{2} (X_{r, g})

as S K_{2} (A_{1}) - S K_{2} (X_{r, g}) = \{\frac{1}{4} (r^{3} - g^{3} + 5 r^{2} + 5 g^{2} - 3 r^{2} g + 3 r g^{2} + 14 r + 2 g - 10 r g + 14)\} - \{\frac{1}{4} (r^{3} - g^{3} + 8 r^{2} + 8 g^{2} - 3 r^{2} g + 3 r g^{2} + 25 r - 9 g - 16 r g)\}

= \frac{1}{4} (- 3 r^{2} - 3 g^{2} - 11 r + 11 g + 6 r g + 14) < 0

Thus, we knew that if

A

has a second or third maximum

S K_{2}

index then the two vertices on

C_{g}

must exist having a degree of at least three.

(a) For

A \neq X_{r, g}

, if

A

has a maximum

S K_{2}

then

C_{g}

cannot have three vertices with a degree of at least 3.

We obtained

X_{r, g}

after several applications of

M_{i}

-transformations

(i \geq 1)

. However, we found a graph with an index less than

X_{r, g}

, we see that

S K_{2} (A) < m a x {S K_{2} (A_{3}), S K_{2} (A_{1})} = S K_{2} (A_{1}) < S K_{2} (X_{r, g})

It implies that

A

has exactly two vertices

m, n

C_{g}

having a degree of at least 3.

Degrees of

m

and

n

must be as:

d (m) = r - g + 1, d (n) = 3

, since other cases cannot hold because if

d (m) = 2

then

A

becomes

X_{r, g}

(since our supposition of degree is at least

3

) and if

d (m) = 4

then

A

cannot become the second maximum because

A

with

d (m) = 3

has a greater index than

A

with

d (m) = 4

Now, if

d (m, n) = 1

then

A = A_{1}

and if

d (m, n) \geq 2

then

A \in Y (r, g)

class including

A_{3}

Lemma 18 implies that extremal graph is

A_{1}

in this case.

(b) For

A \in O_{r, g} \ (A_{1} \cup X_{r, g})

, by the same argument we deduce that

C_{g}

cannot have three vertices with a degree of at least 3, if

A

has a maximum

S K

index, since, in this case, we would have

S K_{2} (A) < S K_{2} (A_{3}) < S K_{2} (A_{1}) < S K_{2} (X_{r, g})

\begin{array}{l} as S K_{2} (A_{3}) - S K_{2} (A_{1}) = {\frac{1}{4} (r^{3} - g^{3} + 5 r^{2} + 5 g^{2} - 3 r^{2} g + 3 r g^{2} + 12 r + 4 g - 10 r g + \\ 16)} - {\frac{1}{4} (r^{3} - g^{3} + 5 r^{2} + 5 g^{2} - 3 r^{2} g + 3 r g^{2} + 14 r + 2 g - 10 r g + 14)} = \frac{1}{4} (- 2 r + \\ 2 g + 2) < 0 \end{array}

It implies that

A

has exactly two vertices

a, b

C_{g}

having a degree of at least 3.

By the same argument (used above),

d (m) = r - g

and

d (n) = 4

d (m, n) = 1

then

A = A_{6}

and if

d (m, n) \geq 2

then

A \in Z (r, g)

class including A₂, which ends the proof. □

(See Figure 10.)

Now we take some graph structures

τ_{1}, τ_{2}, τ_{3}, τ_{4}, τ_{5}, τ_{6}

with order r = 11 and girth g = 5, shown in Figure 11. Numerical values of Shighalli–Kanabur invariants are shown in Table 1 for the above-mentioned graphic structures. We can see that these computations verify our main results in Theorems 3, 6 and 9. We have molecular structures of certain compounds in chemistry which represents some of the graphs of our research as shown in Figure 12.

These structures represents unicyclic graphs having pendant vertices, pendant edges, or pendant paths attached to the vertices of a cycle.

5. Conclusions

In this work, we determined the extremal unicyclic connected graphs of these certain degree-based chemical invariants, i.e., the SK index, the SK₁ index, and the SK₂ index of a given size, order, number of pendant vertices and girth by using some graph transformations. Furthermore, we presented an ordering giving a sequence of unicyclic connected graphs having these indices from greatest in decreasing order.

Author Contributions

Conceptualization, W.H., A.A., S.K., M.A., T.S.S. and X.Z.; methodology, A.A, S.K. and M.A.; validation, W.H., A.A., S.K., M.A., T.S.S. and X.Z.; formal analysis, A.A., S.K., T.S.S. and X.Z.; investigation, W.H., A.A. and S.K.; writing—original draft preparation, W.H., M.A., T.S.S. and X.Z.; writing—review and editing, A.A. and S.K. All authors have read and agreed to the published version of the manuscript.

Funding

This research project is supported by the Natural Science Foundation of Anhui Province Higher School (KJ2021A1154; 2022AH051864).

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest.

References

Topological Indices, and Applications of Graph Theory; Hindawi: London, UK, 2021.
Rouvray, D.H. The Search for Useful Topological Indices in Chemistry: Topological indices promise to have far-reaching applications in fields as diverse as bonding theory, cancer research, and drug design. Am. Sci. 1973, 61, 729–735. [Google Scholar]
Eliasi, M.; Taeri, B. Four new sums of graphs and their Wiener indices. Discret. Appl. Math. 2009, 157, 794–803. [Google Scholar] [CrossRef] [Green Version]
Gutman, I.; Trinajstic, N. Graph theory and molecular orbitals. Total π-electron energy of alternant hydrocarbons. Chem. Phys. Lett. 1972, 17, 535–538. [Google Scholar] [CrossRef]
Khalifeh, M.H.; Yousefi-Azari, H.; Ashrafi, A.R. The first and second Zagreb indices of some graph operations. Discret. Appl. Math. 2009, 157, 804–811. [Google Scholar] [CrossRef] [Green Version]
Ghorbaninejad, M. The Zagreb-coindex of Four Operations on Graphs. Fuzzy Optim. Model. J. 2021, 3, 41–45. [Google Scholar]
Shigehalli, V.; Kanabur, R. New version of degree-based topological indices of certain nanotube. J. Math. Nanosci. 2016, 6, 27–40. [Google Scholar]
Kanabur, R.; Shigehalli, V. Computing Degree-Based Topological Indices of Polyhex Nanotubes. J. Math. Nanosci. 2016, 6, 47–55. [Google Scholar]
Shigehalli, V.S.; Kanabur, R. Computation of New Degree-Based Topological Indices of Graphene. J. Math. 2016, 2016, 4341919. [Google Scholar] [CrossRef]
Kang, S.M.; Zahid, M.A.; Virk, A.U.R.; Nazeer, W.; Gao, W. Calculating the Degree-based Topological Indices of Dendrimers. Open Chem. 2018, 16, 681–688. [Google Scholar] [CrossRef] [Green Version]
Ranjini, P.S.W.; Lokesha, V. SK Indices of Graph Operator S(G) and R(G) on few Nanostructures. Montes Taurus J. Pure Appl. Math. 2020, 2, 38–44. [Google Scholar]
Nurkahli, S.B.; Büyükköse, S. A Note on SK, SK₁ and SK₂ indices of Interval Weighted Graphs. Adv. Inlinear Algebra Matrix Theory 2021, 11, 14. [Google Scholar] [CrossRef]
Roy, K.; Ghosh, G. Exploring QSAR_S with Extended Topochemical Atom (ETA) indices for modeling chemical and drug toxicity. Curr. Pharm. Des. 2010, 16, 2625–2639. [Google Scholar] [CrossRef] [PubMed]
Hosoya, H. Topological index as a sorting device for coding chemical structures. J. Chem. Doc. 1972, 12, 181–183. [Google Scholar] [CrossRef]
Hosoya, H. Graphical enumeration of the coefficients of the secular polynomials of the Hückel molecular orbitals. Theor. Chim. Acta 1972, 25, 215–222. [Google Scholar] [CrossRef]
Tomescu, I.; Kanwal, S. Unicyclic graphs of given girth k = 4 having smallest general sum-connectivity index. Discret. Appl. Math. 2014, 164, 344–348. [Google Scholar] [CrossRef]
Du, Z.; Zhou, B.; Trinajstić, N. Minimum general sum-connectivity index of unicyclic graphs. J. Math. Chem. 2010, 48, 697–703. [Google Scholar] [CrossRef]
Lokesha, V.; Yasmeen, K.Z. SK indices, forgotten topological indices and hyper Zagreb index of Q operator of carbon nanocone. TWMS J. Appl. Eng. Math. 2019, 9, 675–680. [Google Scholar]
Cancan, M.; Ediz, S.; Fareed, S.; Farahani, M.R. More topological indices of generalized prism network. J. Inf. Optim. Sci. 2020, 41, 925–932. [Google Scholar] [CrossRef]

Figure 1. M₁-transformation.

Figure 2. M₂-transformation.

Figure 3. M₃-transformation.

Figure 4. M₄-transformation.

Figure 5. Some graph sets.

Figure 6. Some unicyclic graphs.

Figure 7. Unicyclic graphs having the first and second maximum

S K

index when

g = 3

Figure 7. Unicyclic graphs having the first and second maximum

S K

index when

g = 3

Figure 8. Graphs with the greatest

S K

index.

Figure 8. Graphs with the greatest

S K

index.

Figure 9. Unicyclic connected graphs having the greatest

S K

index.

Figure 9. Unicyclic connected graphs having the greatest

S K

index.

Figure 10. Unicyclic connected graphs having greatest

S K_{1}

and

S K_{2}

indices.

Figure 10. Unicyclic connected graphs having greatest

S K_{1}

and

S K_{2}

indices.

Figure 11. Unicyclic connected graphs having the greatest SK index.

Figure 12. Molecular structures in chemistry.

Table 1. Comparison of different values of the SK, SK₁ and SK₂ indices.

Graphic Structure (τ)	SK (τ)	SK₁ (τ)	SK₂ (τ)
τ₁	33	39	109
τ₂	38	43.5	143.5
τ₃	35	38	115.5
τ₄	38	41	141
τ₅	33	44	107.5
τ₆	43	46	183.5

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2023 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Hui, W.; Aslam, A.; Kanwal, S.; Akram, M.; Shaikh, T.S.; Zuo, X. Ordering Unicyclic Connected Graphs with Girth g ≥ 3 Having Greatest SK Indices. Symmetry 2023, 15, 871. https://doi.org/10.3390/sym15040871

AMA Style

Hui W, Aslam A, Kanwal S, Akram M, Shaikh TS, Zuo X. Ordering Unicyclic Connected Graphs with Girth g ≥ 3 Having Greatest SK Indices. Symmetry. 2023; 15(4):871. https://doi.org/10.3390/sym15040871

Chicago/Turabian Style

Hui, Wang, Adnan Aslam, Salma Kanwal, Mahnoor Akram, Tahira Sumbal Shaikh, and Xuewu Zuo. 2023. "Ordering Unicyclic Connected Graphs with Girth g ≥ 3 Having Greatest SK Indices" Symmetry 15, no. 4: 871. https://doi.org/10.3390/sym15040871

APA Style

Hui, W., Aslam, A., Kanwal, S., Akram, M., Shaikh, T. S., & Zuo, X. (2023). Ordering Unicyclic Connected Graphs with Girth g ≥ 3 Having Greatest SK Indices. Symmetry, 15(4), 871. https://doi.org/10.3390/sym15040871

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Ordering Unicyclic Connected Graphs with Girth g ≥ 3 Having Greatest SK Indices

Abstract

1. Background Survey and Preliminary Results

1.1. Some Graph Transformations

1.2. Certain Unicyclic Graphic Structures

2. Ordering Unicyclic Structures with the Greatest SK Index

3. Ordering Unicyclic Structures with the Greatest SK₁ Index

4. Ordering Unicyclic Structures with the Greatest SK₂ Index

5. Conclusions

Author Contributions

Funding

Institutional Review Board Statement

Informed Consent Statement

Data Availability Statement

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

Article Menu

Ordering Unicyclic Connected Graphs with Girth g ≥ 3 Having Greatest SK Indices

Abstract

1. Background Survey and Preliminary Results

1.1. Some Graph Transformations

1.2. Certain Unicyclic Graphic Structures

2. Ordering Unicyclic Structures with the Greatest SK Index

3. Ordering Unicyclic Structures with the Greatest SK1 Index

4. Ordering Unicyclic Structures with the Greatest SK2 Index

5. Conclusions

Author Contributions

Funding

Institutional Review Board Statement

Informed Consent Statement

Data Availability Statement

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

3. Ordering Unicyclic Structures with the Greatest SK₁ Index

4. Ordering Unicyclic Structures with the Greatest SK₂ Index