# On Minimum Wiener Polarity Index of Unicyclic Graphs with Prescribed Maximum Degree

Authors: Jianping Ou; Xing Feng; Saihua Liu
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

The Wiener polarity index of a connected graphG is defined as the number of its pairs of vertices that are at distance three. By introducing some graph transformations, in different way with that of Huang et al., 2013, we determine the minimum Wiener polarity index of unicyclic graphs with any given maximum degree and girth, and characterize extremal graphs. These observations lead to the determination of the minimum Wiener polarity index of unicyclic graphs and the characterization of the extremal graphs.


---

## Body

## 1. Introduction

All the graphs considered in this paper are connected and simple. The distance between two verticesu and v of a graph G, denoted by d
G
(
u
,
v
) or d
(
u
,
v
) for short, is the length of a shortest path connecting these two vertices. The Wiener polarity index of a graph G is defined as the number of its unordered pairs of vertices that has distance three [1]. Namely, the Wiener polarity index of a molecular graph G is
(1)
W
P
(
G
)
=
u
,
v
:
d
G
u
,
v
=
3
,
u
,
v
∈
V
G
.In 1998, by using the Wiener polarity index, Lukovits and Linert in [2] demonstrated quantitative structure-property relationships in a series of acyclic and cycle-containing hydrocarbons. Besides, a physicochemical interpretation of W
P
(
G
) was found by Rouvray and King [3]. M. Liu and B. Liu described the relations between Wiener polarity index, Zagreb index, Wiener index, and hyper-Wiener index in [4]; they also determined there the first two smallest Wiener polarity indices among all unicyclic graphs. Recently, Du et al. obtained the smallest and largest Wiener polarity indices together with the corresponding graphs among all trees with any given number of vertices [5]. In [6], Deng and Xiao, determined the maximum Wiener polarity index of trees with k pendants and characterized the extremal graphs. In [7], the authors determined the Wiener polarity of fullerenes and hexagonal systems. In [8], Hou et al. determine the maximum wiener polarity index of unicyclic graphs and characterizes the corresponding extremal graphs. This work determines in differrent way with that of [9] the minimum Wiener polarity index of unicyclic graphs with any given maximum degree and girth; these observations lead to the determination of minimum wiener polarity index and the characterization of the corresponding extremal graphs.Before proceeding, let us introduce some more symbols and terminology. Denote byN
G
(
u
), or N
(
G
) for short, the neighborhood of vertex u in graph G, the set of vertices adjacent to u. Let d
G
(
u
)
=
d
(
u
)
=
N
G
u represent the degree of vertex u in graph G. If d
(
u
)
=
1, vertex u is called a pendent vertex. The girth g
(
G
) of a unicyclic graph G is the length of its unique cycle. As usual, let C
n, S
n, and P
n represent a cycle, a star, and a path on n vertices, respectively, and U
n
,
Δ the set of unicyclic graphs with n vertices and maximum degree Δ. For any unicyclic graph G and any vertex v in its cycle C, the union of vertex v and the component of G
-
V
(
C
) that has a vertex u adjacent to v induces a tree in G, which is called a hanging tree on vertex v and is denoted by T
[
v
]. The union of all these hanging trees T
[
v
] is denoted by U
T
[
v
]. For other symbols and terminology not specified herein, we follow that of [10].


## 2. Property of Graph Transformations

Letn
1
,
n
2
≥
0 be two integers. After joining n
1 and n
2 vertices, each by an edge, to the two endpoints of a path P
n,, respectively, we obtain a new graph and denote it by S
n
1
,
n
2
n [11]. For example, the path on two vertices may be regarded as S
0,0
2, and the star S
n with n
≥
4 may be regarded as S
1
,
n
-
2
1. Denote by T
n
,
Δ the set of trees with order n (n vertices) and maximum degree Δ.LetC
=
v
1
v
2
⋯
v
g
v
1 be a cycle with g
≥
3 and let m
1
,
m
2
,
…
,
m
g be nonnegative integers. We attach at first m
i isolated vertices to vertex v
i for every i
∈
{
2,3
,
4
,
…
,
g
}. And then past a 1-degree vertex of a star that has m
1
+
2 vertices to vertex v
1 to obtain a graph denoted by U
n
,
g
,
Δ
,
1
m
1
,
m
2
,
…
,
m
g, where n denotes the number of vertices of the obtained graph; or attach m
1 isolated vertices directly to vertex v
1 to obtain graph U
n
,
g
,
Δ
,
0
m
1
,
m
2
,
…
,
m
g; or past the 1-degree vertex of S
1
,
m
1
n
1
-
m
1
-
1 whose neighbor has degree two to v
1 to obtain graph U
n
,
g
,
Δ
,
n
1
-
m
1
-
1
m
1
,
m
2
,
…
,
m
g. It is not difficult to see that m
i
≤
Δ
-
2 for every i with 2
≤
i
≤
g, m
1
≤
Δ
-
2 for the second case and m
1
≤
Δ
-
1 for the other two cases. Furthermore, either m
1
=
Δ
-
1, or m
1
=
Δ
-
2, or m
i
=
Δ
-
2 for some i
≥
2.Finally, letU
n
,
g
,
Δ
,
n
1
-
m
1
-
1
m
1
,
m
2 denote the graph obtained by attaching at first m
2 isolated vertices to vertex v
1 and then pasting the 1-degree vertex of S
1
,
m
1
n
1
-
m
1
-
1 whose neighbor has degree two (if S
1
,
m
1
n
1
-
m
1
-
1 contains such pendent vertex) to v
1. For clarity, we depict some of these graphs in Figure 1.Figure 1Lemma 1 (see [11]).
IfT
∈
T
n
,
Δ and 3
≤
Δ
≤
n
-
2, then W
P
(
T
)
≥
n
-
3, with the equality holding if and only if T
=
S
Δ
-
1
,
l
n
-
Δ
-
l
+
1, where 0
≤
l
≤
min
⁡
{
Δ
-
1
,
n
-
Δ
-
2
}.Lemma 2 (see [11]).
W
P
(
P
n
)
=
n
-
3; W
P
(
S
n
)
=
0.In what follows, for clarity, we denote byC
=
v
1
v
2
⋯
v
g
v
1 the unique cycle of any graph U
∈
U
n
,
Δ with girth g.Lemma 3.
LetU
∈
U
n
,
Δ and T
[
v
i
] be one of its hanging tree. If 3
≤
Δ
i
≤
n
i
-
2 and T
[
v
i
]
≠
S
1
,
Δ
i
-
1
n
i
-
Δ
i, then W
p
(
U
′
)
<
W
p
(
U
), where n
i
=
|
T
[
v
i
]
|, Δ
i is the maximum degree of T
[
v
i
], and U
′ is obtained from U by transforming T
[
v
i
] to T
=
S
1
,
Δ
i
-
1
n
i
-
Δ
i with d
T
(
v
i
)
=
1 and the neighbor of v
i in T having degree two if T contains such pendent vertices.Proof.
LetN
T
[
v
i
]
(
v
i
)
=
{
u
i
} and N
T
(
v
i
)
=
{
u
i
′
}. If a unicyclic graph G has cycle C, then its wiener polarity index can be expressed as (refer to [4] for example)
(2)
W
P
G
=
∑
u
v
∈
E
G
d
u
-
1
d
v
-
1
,
if
g
≥
7
;
∑
u
v
∈
E
G
d
u
-
1
d
v
-
1
-
3
,
if
g
=
6
;
∑
u
v
∈
E
G
d
u
-
1
d
v
-
1
-
5
,
if
g
=
5
;
∑
u
v
∈
E
G
d
u
-
1
d
v
-
1
-
∑
u
∈
V
C
d
u
+
4
,
if
g
=
4
;
∑
u
v
∈
E
G
-
E
C
d
u
-
1
d
v
-
1
+
∑
u
v
∈
E
C
d
u
-
2
d
v
-
2
,
if
g
=
3
.
Notice that ifH is a tree, then its wiener polarity index can be expressed as W
P
(
H
)
=
∑
u
v
∈
E
(
H
)
(
d
(
u
)
-
1
)
(
d
(
v
)
-
1
). According to the differences between T and T
[
v
i
], it is not difficult to deduce (for simplicity the common terms are deleted, this method is also employed in the proof of other leammas) that
(3)
W
P
U
′
-
W
P
U
=
W
P
T
+
d
T
u
i
′
-
1
d
U
′
v
i
-
1
-
W
P
T
v
i
-
d
T
v
i
u
i
-
1
d
U
v
i
-
1
.
Since Δ
i
≤
n
i
-
2, it follows that d
T
(
u
i
′
)
=
2. Combining this observation with d
U
(
v
i
)
=
d
U
′
(
v
i
), d
T
[
v
i
]
(
u
i
)
≥
2, Lemmas 1 and 2 and the fact that among trees with maximun degree Δ
i
=
n
i
-
2 and order n
i graph S
1
,
Δ
i
-
1
2 has maximum wiener polarity index, we deduce that
(4)
W
P
U
′
-
W
P
U
=
W
P
T
-
W
P
T
v
i
+
2
-
d
T
v
i
u
i
d
U
v
i
-
1
≤
W
P
T
-
W
P
T
v
i
≤
0
.
Again by Lemmas 1 and 2, the inequalities in above formula become equalities if and only if T
[
v
i
]
=
S
t
,
Δ
i
-
1
n
i
-
Δ
i
-
t
+
1 for some positive integer t
≤
Δ
i
-
1 and d
T
[
v
i
]
(
u
i
)
=
2. So, t
=
1 and the lemma follows.Lemma 4.
LetU
∈
U
n
,
Δ and T
[
v
i
] be one of its hanging tree. If U
′ is obtained from U by transforming T
[
v
i
] to T
=
P
n
i then W
P
(
U
′
)
≤
W
P
(
U
), with equality holding if and only if T
[
v
i
]
=
S
1
,
l
n
i
-
l
-
1 with d
T
[
v
i
]
(
v
i
)
=
1 and the neighbor of v
i in T
[
v
i
] having degree two.Proof.
LetN
T
[
v
i
]
(
v
i
)
=
{
u
i
} and N
T
(
v
i
)
=
{
u
i
′
}. According to the differences between T and T
[
v
i
] and formula (2), it is not difficult to deduce that
(5)
W
P
U
′
-
W
P
U
=
W
P
T
+
d
T
u
i
′
-
1
d
U
′
v
i
-
1
-
W
P
T
v
i
-
d
T
v
i
u
i
-
1
d
U
v
i
-
1
.
Since d
U
(
v
i
)
=
d
U
′
(
v
i
), d
T
(
u
i
′
)
=
2 and d
T
[
v
i
]
(
u
i
)
≥
2, from Lemmas 1 and 2 it follows that
(6)
W
P
U
′
-
W
P
U
=
W
P
T
-
W
P
T
v
i
+
2
-
d
T
v
i
u
i
d
U
v
i
-
1
.
Notice thatT
[
v
i
]
≠
P
n
i implies n
i
≥
4. If diameter d
(
T
[
v
i
]
)
=
2 and T
[
v
i
] is not a path, then n
i
≥
4, d
T
[
v
i
]
(
u
i
)
=
n
i
-
1 and W
P
(
T
[
v
i
]
)
=
0. So,
(7)
W
P
U
′
-
W
P
U
=
n
i
-
3
-
n
i
-
3
d
U
v
i
-
1
=
n
i
-
3
d
U
v
i
-
2
<
0
.
If diameter d
(
T
[
v
i
]
)
≥
3 but either T
[
v
i
]
≠
S
1
,
l
n
i
-
l
-
1 or T
[
v
i
]
=
S
1
,
l
n
i
-
l
-
1 with d
T
[
v
i
]
(
u
i
)
≥
3, then W
P
(
T
)
-
W
P
(
T
[
v
i
]
)
≤
0, (
2
-
d
T
[
v
i
]
(
u
i
)
)
(
d
U
(
v
i
)
-
1
)
≤
0, and at least one of these two inequalities strictly holds. By formula (6), we also have W
P
(
U
′
)
-
W
P
(
U
)
<
0. Hence, the lemma follows.Lemma 5.
LetU
∈
U
n
,
Δ be a unicylic graph with girth g
≥
5. If its hanging trees are T
i
=
S
1
,
Δ
i
-
1
n
i
-
Δ
i, i
=
1
,
…
,
m
≥
2 and max
⁡
{
Δ
1
,
…
,
Δ
m
}
=
Δ, then W
P
(
U
′
)
≤
W
P
(
U
), where U
′ is obtained from U by transforming U
-
E
(
C
) to a hanging tree T
=
S
1
,
Δ
-
1
∑
i
=
1
m
n
i
-
Δ
-
m
+
1 on any vertex v
i with d
T
(
v
i
)
=
1 and the neighbor of v
i in T having degree two.Proof.
Assume without loss of generality thatΔ
1
=
Δ and T
1 is a hanging tree on v
1. After tranforming every hanging tree T
j
≠
T
1 of U to a path P
n
j, we obtain a new graph U
2
∈
U
n
,
Δ. By Lemma 4 we have W
P
(
U
2
)
≤
W
P
(
U
).
LetN
(
v
1
)
=
{
v
2
,
v
g
,
u
11
,
…
,
u
1
m
1
}. If U
2 has a hanging tree P
=
v
1
u
1
i
⋯
u
t
i on vertex v
1, let U
3
=
U
2
-
v
1
u
11
+
u
11
u
t
i, where u
11 is the neighbor of v
1 in T
1. Since d
U
2
(
v
1
)
=
d
U
3
(
v
1
)
+
1, d
U
2
(
u
t
i
)
=
1, d
U
3
(
u
t
i
)
=
2
=
d
U
3
(
u
11
)
=
d
U
3
(
u
t
-
1
,
i
), and g
≥
5, it follows from formula (2) that when t
≥
2,
(8)
W
P
U
2
-
W
P
U
3
=
∑
j
=
1
m
1
d
U
2
u
1
j
-
1
d
U
2
v
1
-
1
+
d
U
2
v
1
-
1
d
U
2
v
2
-
1
+
d
U
2
v
g
-
1
-
d
U
3
u
11
-
1
d
U
3
u
t
i
-
1
-
d
U
3
u
t
i
-
1
d
U
3
u
t
-
1
,
i
-
1
-
∑
j
=
2
m
1
d
U
3
u
1
j
-
1
d
U
3
v
1
-
1
-
d
U
3
v
1
-
1
d
U
3
v
2
-
1
+
d
U
3
v
g
-
1
=
∑
j
=
2
m
1
d
U
3
u
1
j
-
1
+
d
U
3
v
2
+
d
U
3
v
g
-
2
+
d
U
2
u
11
-
1
d
U
2
v
1
-
1
-
2
>
0
;
when t
=
1, since d
U
3
(
u
1
i
)
=
2 and d
U
2
(
u
11
)
=
d
U
3
(
u
11
), we have
(9)
W
P
U
2
-
W
P
U
3
=
∑
j
=
1
m
1
d
U
2
u
1
j
-
1
d
U
2
v
1
-
1
+
d
U
2
v
1
-
1
d
U
2
v
2
-
1
+
d
U
2
v
g
-
1
-
d
U
3
u
11
-
1
d
U
3
u
1
i
-
1
-
∑
j
=
2
m
1
d
U
3
u
1
j
-
1
d
U
3
v
1
-
1
-
d
U
3
v
1
-
1
d
U
3
v
2
-
1
+
d
U
3
v
g
-
1
=
∑
j
=
2
j
≠
i
m
1
d
U
3
u
1
j
-
1
+
d
U
3
v
2
+
d
U
3
v
g
-
2
+
d
U
2
u
11
-
1
d
U
2
v
1
-
1
-
d
U
3
u
11
-
1
-
d
U
3
u
1
i
-
1
d
U
3
v
1
-
1
=
∑
j
=
2
j
≠
i
m
1
d
U
3
u
1
j
-
1
+
d
U
3
v
2
+
d
U
3
v
g
-
2
+
d
U
2
u
11
-
2
d
U
2
v
1
-
2
>
0
.
By induction on the number of hanging trees on vertex v
1, it follows that if we denote by U
4 the graph obtained from U
2 by transforming U
T
[
v
1
] to T
′
=
S
1
,
Δ
n
′
-
Δ
-
1 then W
P
(
U
4
)
<
W
P
(
U
2
) when U
2 has at least two hanging trees on vertex v
1, where n
′
=
U
T
v
1.
In the same way, one can show with ease that if one hanging treeP
=
v
i
⋯
y of U
4 on vertex v
i has at least three vertices, then the graph U
4
-
v
1
x
+
x
y has less wiener polarity index than that of U
4, where x is the neighbor of v
1 in T
′. And so, we leave its proof to the readers.
Now, we consider the case when every hanging tree ofU
4 on vertices v
i, i
≠
1, is a path of order two. Let d
U
4
(
v
j
)
=
m
j
+
2, j
≥
2 and assume without loss of generality that m
i
≥
2, where i
≥
2. Denote by U
5 the graph obtained from U
4 by transforming U
T
[
v
i
] to a path of order m
i. Then
(10)
W
P
U
4
-
W
P
U
5
=
m
i
m
i
-
1
+
m
i
+
1
+
2
-
m
i
-
1
+
m
i
+
1
+
2
-
2
-
m
i
-
2
=
m
i
-
1
m
i
-
1
+
m
i
+
1
+
m
i
-
2
≥
0
.
In conclusion, ifU
6 is the graph obtained from U
4 by transforming U
T
[
v
i
] to a path of order U
T
v
i for every i
≥
2, then W
P
(
U
6
)
≤
W
P
(
U
4
).
Finally, ifN
U
6
(
v
1
)
=
{
v
2
,
v
g
,
x
} and U
6 has a hanging tree P
t
=
v
i
u
2
u
3
⋯
u
t on vertex v
i with i
≥
2, then let U
7
=
U
6
-
v
1
x
+
x
u
t. Since the total contribution of x and its neighbor in T
[
v
1
]
-
v
1 to W
P
(
U
6
) is not less than the total contribution of them to W
P
(
U
7
), furthermore, the contribution of other vertex to W
P
(
U
6
) is not less than the contribution of its corresponding vertex to W
P
(
U
7
), it follows that W
P
(
U
7
)
≤
W
P
(
U
6
). And so, the lemma follows.Lemma 6.
LetU
∈
U
n
,
Δ be a unicylic graph with girth g
=
4. If its hanging trees are T
i
=
S
1
,
Δ
i
-
1
n
i
-
Δ
i, i
=
1
,
…
,
m
≥
2, max
⁡
{
Δ
1
,
…
,
Δ
m
}
=
Δ, and U
≠
U
n
,
4
,
Δ
,
n
-
m
3
-
Δ
-
3
Δ
-
1,0
,
m
3
,
0 then W
P
(
U
′
)
≤
W
P
(
U
), where U
′ is obtained from U by transforming U
-
E
(
C
) to a hanging tree T
=
S
1
,
Δ
-
1
∑
i
=
1
m
n
i
-
Δ
-
m
+
1 on any vertex v
j with d
T
(
v
j
)
=
1 and the neighbor of v
j in T having degree two.Proof.
Assume without loss of generality thatΔ
1
=
Δ and T
1 is a hanging tree on v
1. After tranforming every hanging tree T
i
≠
T
1 of U to a path P
n
i, we obtain a new graph U
2
∈
U
n
,
Δ. By Lemma 4 we have W
P
(
U
2
)
≤
W
P
(
U
).
LetN
(
v
1
)
=
{
v
2
,
v
g
,
u
11
,
…
,
u
1
m
1
}. If U
2 has a hanging tree P
=
v
1
u
1
i
⋯
u
t
i on vertex v
1, let U
3
=
U
2
-
v
1
u
11
+
u
11
u
t
i, where u
11 is the neighbor of v
1 in T
1. Since d
U
2
(
v
1
)
=
d
U
3
(
v
1
)
+
1, d
U
2
(
v
t
i
)
=
1, d
U
3
(
u
t
i
)
=
2, and g
=
4, it follows from formula (2) that when t
≥
2,
(11)
W
P
U
2
-
W
P
U
3
=
∑
j
=
1
m
1
d
U
2
u
1
j
-
1
d
U
2
v
1
-
1
+
d
U
2
v
1
-
1
d
U
2
v
2
-
1
+
d
U
2
v
g
-
1
-
d
U
3
u
11
-
1
d
U
3
u
t
i
-
1
-
d
U
3
u
t
i
-
1
d
U
3
u
t
-
1
,
i
-
1
-
∑
j
=
2
m
1
d
U
3
u
1
j
-
1
d
U
3
v
1
-
1
-
d
U
3
v
1
-
1
d
U
3
v
2
-
1
+
d
U
3
v
g
-
1
+
1
=
∑
j
=
2
m
1
d
U
3
u
1
j
-
1
+
d
U
3
v
2
+
d
U
3
v
g
-
2
+
d
U
2
u
11
-
1
d
U
2
v
1
-
2
-
1
>
0
.
Whent
=
1, since d
U
3
(
u
1
i
)
=
2 and d
U
2
(
u
11
)
=
d
U
3
(
u
11
), we have
(12)
W
P
U
2
-
W
P
U
3
=
∑
j
=
1
m
1
d
U
2
u
1
j
-
1
d
U
2
v
1
-
1
+
d
U
2
v
1
-
1
d
U
2
v
2
-
1
+
d
U
2
v
g
-
1
-
d
U
3
u
11
-
1
d
U
3
u
1
i
-
1
-
∑
j
=
2
m
1
d
U
3
u
1
j
-
1
d
U
3
v
1
-
1
-
d
U
3
v
1
-
1
d
U
3
v
2
-
1
+
d
U
3
v
g
-
1
+
1
=
∑
j
=
2
j
≠
i
m
1
d
U
3
u
1
j
-
1
+
d
U
3
v
2
+
d
U
3
v
g
-
2
+
d
U
2
u
11
-
1
d
U
2
v
1
-
1
-
d
U
3
u
11
-
1
-
d
U
3
u
1
i
-
1
d
U
3
v
1
-
1
+
1
=
∑
j
=
2
j
≠
i
m
1
d
U
3
u
1
j
-
1
+
d
U
3
v
2
+
d
U
3
v
g
-
2
+
d
U
2
u
11
-
2
d
U
2
v
1
-
2
+
1
>
0
.
By induction on the number of hanging trees on vertex v
1, it follows that if we denote by U
4 the graph obtained from U
2 by transforming U
T
[
v
1
] to T
′
=
S
1
,
Δ
-
1
n
′
-
Δ then W
P
(
U
4
)
<
W
P
(
U
2
) when U
2 has at least two hanging trees on vertex v
1, where n
′
=
U
T
v
1.
In the same way, one can show with ease that if one hanging treeP
=
v
i
⋯
y of U
4 on vertex v
i has at least three vertices, then the graph U
4
-
v
1
x
+
x
y has less wiener polarity index than that of U
4, where x is the neighbor of v
1 in T
′. And so, we leave its proof to the readers.
Now, we consider the case when every hanging tree ofU
4 on vertices v
i, i
≠
1, is a path of order two. Let P
=
v
i
w be a hanging tree of U
4. If i
∈
{
2,4
}, say i
=
2, let U
5
=
U
4
-
v
2
w
-
v
1
x
+
v
1
w
+
w
x and m
j
=
d
U
4
(
v
j
)
+
2, then from formula (2) we deduce that
(13)
W
P
U
4
-
W
P
U
5
=
m
3
+
1
m
2
+
1
+
2
m
2
+
1
+
2
d
U
4
x
-
1
-
m
3
+
1
m
2
-
2
m
2
-
2
d
U
5
w
-
1
-
d
U
5
w
-
1
d
U
5
x
-
1
+
1
=
m
3
+
d
U
4
x
+
1
>
0
.
The second equality holds since d
U
4
(
x
)
=
d
U
5
(
x
) and d
U
5
(
w
)
=
2. And so, the lemma follows.Lemma 7.
LetU
∈
U
n
,
Δ be a unicylic graph with girth g
=
3. If one of its hanging tree is T
1
=
S
1
,
Δ
-
1
n
1
-
Δ and all others are paths, and U
∉
{
U
n
,
3
,
Δ
,
n
-
m
1
-
Δ
-
2
Δ
-
1
,
m
1
,
0
,
U
n
,
3
,
Δ
,
n
-
m
2
-
Δ
-
2
Δ
-
1
,
m
2
} then W
P
(
U
′
)
≤
W
P
(
U
), where U
′ is obtained from U by transforming U
-
E
(
C
) to a hanging tree T
=
S
1
,
Δ
-
1
n
-
Δ
-
2 on any vertex v
j with d
T
(
v
j
)
=
1 and the neighbor of v
j in T having degree two, n
-
m
2
-
Δ
-
2
≥
2 and m
2
≤
Δ
-
3.Proof.
Assume without loss of generality thatT
1 is a hanging tree on v
1. Consider at first the case when U has at least two hanging trees on vertex v
1. Let N
(
v
1
)
=
{
v
2
,
v
3
,
u
11
,
…
,
u
1
m
1
}. If P
=
v
1
u
1
i
⋯
u
t
i is a longest hanging tree of U on vertex v
1, let U
1
=
U
-
v
1
u
11
+
u
11
u
t
i, where u
11 is the neighbor of v
1 in T
1. Since d
U
(
v
1
)
=
d
U
1
(
v
1
)
+
1, d
U
(
u
t
i
)
=
1, and d
U
1
(
u
t
i
)
=
2, it follows from formula (2) that when t
≥
2 we have
(14)
W
P
U
-
W
P
U
1
=
∑
j
=
1
m
1
d
U
u
1
j
-
1
d
U
v
1
-
1
+
d
U
v
1
-
2
d
U
v
2
-
2
+
d
U
v
3
-
2
-
d
U
1
u
11
-
1
d
U
1
u
t
i
-
1
-
d
U
1
u
t
i
-
1
d
U
1
u
t
-
1
,
i
-
1
-
∑
j
=
2
m
1
d
U
1
u
1
j
-
1
d
U
1
v
1
-
1
-
d
U
1
v
1
-
2
d
U
1
v
2
-
2
+
d
U
1
v
3
-
2
=
∑
j
=
2
m
1
d
U
u
1
j
-
1
+
d
U
v
2
+
d
U
v
3
-
4
+
d
U
u
11
-
1
d
U
v
1
-
1
-
2
>
0
;
and that when t
=
1, since d
U
1
(
u
1
i
)
=
2, d
U
(
u
1
i
)
=
1 and d
U
(
u
11
)
=
d
U
1
(
u
11
), we have
(15)
W
P
U
-
W
P
U
1
=
∑
j
=
1
m
1
d
U
u
1
j
-
1
d
U
v
1
-
1
+
d
U
v
1
-
2
d
U
v
2
-
2
+
d
U
v
3
-
2
-
d
U
1
u
11
-
1
d
U
1
u
1
i
-
1
-
∑
j
=
2
m
1
d
U
1
u
1
j
-
1
d
U
1
v
1
-
1
-
d
U
1
v
1
-
2
d
U
1
v
2
-
2
+
d
U
1
v
3
-
2
=
∑
j
=
2
j
≠
i
m
1
d
U
u
1
j
-
1
+
d
U
v
2
+
d
U
v
3
-
4
+
d
U
u
11
-
1
d
U
v
1
-
1
-
d
U
1
u
11
-
1
-
d
U
1
u
1
i
-
1
d
U
1
v
1
-
1
=
∑
j
=
2
j
≠
i
m
1
d
U
u
1
j
-
1
+
d
U
v
2
+
d
U
v
3
-
4
+
d
U
u
11
-
2
d
U
v
1
-
2
≥
0
.
The above inequality becomes equality if and only if d
U
(
u
1
j
)
=
1 for every j
≠
1, d
U
(
v
2
)
=
d
U
(
v
3
)
=
2 and d
U
(
u
11
)
=
2, namely, U
=
U
n
,
3
,
Δ
,
n
-
m
2
-
Δ
-
2
Δ
-
1
,
m
2 with n
-
m
2
-
Δ
-
2
≥
2 and m
2
≤
Δ
-
3.
By induction on the number of hanging trees on vertexv
1, it follows that if we denote by U
2 the graph obtained from U by transforming U
T
[
v
1
] to S
1
,
Δ
-
1
n
′
-
Δ then W
P
(
U
2
)
≤
W
P
(
U
), where n
′
=
U
T
v
1.
Consider secondly the case whenT
1 is the unique hanging tree of U on vertex v
1. By similar reasoning as above, one can show with ease that if one hanging tree of U on vertex v
i has at least three vertices, then the graph obtained from U by transforming U
T
[
v
i
] to a path of order U
T
v
i has less wiener polarity index than that of U. And so, we assume in what follows that every hanging tree of U on vertices v
i, i
≠
1, is a path of order two.
Letd
U
(
v
j
)
=
s
j
+
2. Since U
∉
{
U
n
,
3
,
Δ
,
n
-
m
1
-
Δ
-
2
Δ
-
1
,
m
1
,
0
,
U
n
,
3
,
Δ
,
n
-
m
2
-
Δ
-
2
Δ
-
1
,
m
2
}, it follows that s
2
,
s
3
≥
1 and s
1
=
1. Let x be the neighbor of v
1 in T
1, y be the neighbor of v
1 in T, where T and T
1 are postulated in the lemma. Noticing that if n
-
Δ
-
s
2
-
s
3
-
2
=
1 then W
P
(
T
1
)
=
0 and W
P
(
T
)
=
T
′
-
3
=
s
2
+
s
3
+
Δ
-
2, and that if n
-
Δ
-
s
2
-
s
3
-
2
≥
2 then W
P
(
T
)
-
W
P
(
T
1
)
=
s
2
+
s
3, we deduce from formula (2) that
(16)
W
P
U
-
W
P
U
′
=
s
2
s
3
+
s
2
+
s
3
+
d
U
v
1
-
1
d
U
x
-
1
+
W
P
T
1
-
d
U
′
v
1
-
1
d
U
′
y
-
1
-
W
P
T
=
s
2
s
3
+
s
2
+
s
3
-
1
+
2
Δ
-
1
-
s
2
+
s
3
+
Δ
-
2
,
if
n
-
Δ
-
s
2
-
s
3
-
2
=
1
;
2
-
s
2
+
s
3
,
if
n
-
Δ
-
s
2
-
s
3
-
2
≥
2
≥
s
2
s
3
+
1
>
0
.
And so, the lemma follows.Lemma 8.
LetU
∈
U
n
,
Δ. If every hanging tree is a path then W
P
U
′
<
W
P
(
U
), where U
′ is obtained from U by transforming U
T
[
v
i
] to S
1
,
Δ
i
-
3
n
i
-
Δ
i
+
2 with d
U
′
(
v
i
)
=
Δ
i
=
d
U
(
v
i
) and n
i
=
U
T
v
i.Proof.
Assume without loss of generality thati
=
1. Let N
(
v
1
)
=
{
v
2
,
v
g
,
u
11
,
…
,
u
m
1
}, and let P
t
+
1
=
v
1
u
11
⋯
u
1
t be a hanging tree on v
1 that has maximum length. If P
s
+
1
=
v
1
u
21
⋯
u
2
s is another hanging tree on v
1 with s
≥
2, let U
1
=
U
-
u
21
u
22
+
u
22
u
1
t, since d
U
1
(
u
1
(
t
-
1
)
)
=
d
U
1
(
u
1
t
)
=
2 it follows that
(17)
W
P
U
1
-
W
P
U
=
d
U
1
u
1
t
-
1
-
1
d
U
1
u
1
t
-
1
-
d
U
v
1
-
1
=
2
-
d
U
v
1
<
0
.
And so, the lemma follows by induction on the number of hanging trees on vertex v
1 that has length of at least three.


## 3. Minimum Index and Extremal Graphs with Any Given Girth

This section charaterizes the extremal unicyclic graphs with any given girth and minimum wiener polarity index. To this end, we first consider the case when the maximum degree vertices are contained in the cycle and then compare the results with those obtained in the previous section. Since there is only one unicyclic graph that has maximum degreeΔ, girth g, and n
=
Δ
+
g
-
2 vertices, we need to only consider the case when a unicyclic graph has at least n
≥
Δ
+
g
-
1 vertices.Lemma 9.
LetU
∈
U
n
,
Δ be a unnicylic graph with girth g
=
3 and n
≥
Δ
+
3 vertices. If d
(
v
1
)
=
Δ and every hanging tree of U is a path then W
P
(
U
)
≥
n
-
3, with equality if and only if U
∈
{
U
n
,
3
,
Δ
,
n
-
Δ
-
1
1
,
Δ
-
3
,
U
n
,
3
,
Δ
,
n
-
Δ
-
2
1
,
Δ
-
2,0
}.Proof.
The lemma is clearly true whenn
=
Δ
+
3 since there are only five nonisomorphic unicyclic graphs in this subcase. So, assume in what follows that n
≥
Δ
+
4. Let N
(
v
1
)
=
{
v
2
,
v
3
,
u
11
,
…
,
u
(
Δ
-
2
)
1
}, U
T
[
v
1
]
=
S
1
,
Δ
-
3
n
1
-
Δ
+
2, and P
=
v
1
u
11
⋯
u
1
t be the longest hanging tree on v
1.
Let us consider at first the case whent
=
1. In this case, every hanging tree on v
1 is a path on two vertices. To prove the lemma, we may assume in what follows that U is an extremal unicyclic graph with minimum wiener polarity index. If the total number of hanging trees on vertices v
2 and v
3 is at least two, assume without loss of generality that P
1
=
v
2
u
21
⋯
u
2
s and P
2
=
v
3
u
31
⋯
u
3
l are two of these hanging trees. Let U
1
=
U
-
v
3
u
31
+
u
31
u
2
s. When s or l
≥
2, say s
≥
2, by formula (2) we have
(18)
W
P
U
-
W
P
U
1
=
d
U
v
1
-
2
+
d
U
v
2
-
2
+
d
U
u
31
-
1
d
U
v
3
-
1
-
d
U
1
u
31
-
1
d
U
1
u
2
s
-
1
-
d
U
1
u
2
s
-
1
-
1
d
U
1
u
2
s
-
1
.
Since d
U
(
u
31
)
=
d
U
1
(
u
31
)
=
d
U
1
(
u
2
s
)
=
2 and d
U
(
v
2
)
,
d
U
(
v
3
)
≥
3, it follows that W
P
(
U
)
-
W
P
(
U
1
)
≥
2 in this subcase, which is a contradiction since U is an extremal graph. By induction on the total number of hanging trees on vertices v
2 and v
3, we deduce that U
=
U
n
,
3
,
Δ
,
n
-
Δ
-
2
1
,
Δ
-
2,0 in this subcase.
When every hanging tree on verticesv
2 or v
3 is a path on two vertices, which implies that s
=
l
=
1, we deduce that d
(
v
2
)
≥
4 or d
(
v
3
)
≥
4 since n
≥
Δ
+
4. And so d
(
v
1
)
≥
4. Assume without loss of generality that d
(
v
2
)
≥
4 and {
v
2
u
,
v
2
w
}
∈
E
(
U
)
-
E
(
C
). Let U
1
=
U
-
v
2
u
+
u
w. Similar to the reasoning employed in the proof of formula (18), we have
(19)
W
P
U
-
W
P
U
1
=
d
U
v
1
-
2
+
d
U
v
2
-
2
-
2
≥
0
.
Now, U
1 becomes the first subcase. And so, the lemma is ture in the first case.
Secondly, we consider the case whent
≥
2. If U has a hanging tree on v
2 or v
3, say P
=
v
2
u
21
⋯
u
2
s, let U
1
=
U
-
v
2
u
21
+
u
21
u
1
t. As in the proof of formula (18), we have
(20)
W
P
U
-
W
P
U
1
=
d
U
v
1
-
2
+
d
U
v
3
-
2
+
d
U
u
21
-
1
d
U
v
2
-
1
-
d
U
1
u
21
-
1
d
U
1
u
1
t
-
1
-
d
U
1
u
1
t
-
1
-
1
d
U
1
u
1
t
-
1
.
Since d
U
1
(
u
21
)
=
d
U
(
u
21
), d
U
1
(
u
1
(
t
-
1
)
)
=
d
U
1
(
u
1
t
)
=
2, it follows that
(21)
W
P
U
-
W
P
U
1
=
d
U
v
1
-
2
+
d
U
v
3
-
2
+
d
U
u
21
-
1
d
U
v
2
-
2
-
1
.
Since d
U
(
u
21
)
≥
1, d
U
(
v
2
)
≥
3, d
U
(
v
1
)
≥
3, and d
U
(
v
3
)
≥
2 in this case, it follows that W
P
(
U
)
-
W
P
(
U
1
)
≥
0, with the equality holding if and only if d
(
v
3
)
=
2, d
(
v
1
)
=
3 and s
=
1. Therefore, U
=
U
n
,
3
,
Δ
,
n
-
Δ
-
1
1
,
Δ
-
3. By formula (2) it is not difficult to show that W
P
(
U
n
,
3
,
Δ
,
n
-
Δ
-
1
1
,
Δ
-
3
)
=
W
P
(
U
n
,
3
,
Δ
,
n
-
Δ
-
2
1
,
Δ
-
2,0
)
=
n
-
3. And so, the lemma follows.Lemma 10.
LetU
∈
U
n
,
Δ be a unnicylic graph with girth g
=
3 and n
=
Δ
+
2 vertices. If d
(
v
1
)
=
Δ and every hanging tree of U is a path then W
P
(
U
)
≥
n
-
4, with equality if and only if U
∈
U
Δ
+
2,3
,
Δ
,
0
Δ
-
2,1
,
0.Proof.
Since there are only two graphs that satisfy the postulated conditions, namely,U
∈
{
U
Δ
+
2,3
,
Δ
,
0
Δ
-
2,1
,
0
,
U
Δ
+
2,3
,
Δ
,
1
1
,
Δ
-
3
}, W
P
(
U
Δ
+
2,3
,
Δ
,
0
Δ
-
2,1
,
0
)
=
n
-
4, and W
P
(
U
Δ
+
2,3
,
Δ
,
1
1
,
Δ
-
3
)
=
n
-
3, the lemma follows.Lemma 11.
LetU
∈
U
n
,
Δ be a unicyclic graph with girth g
=
4 and n
≥
Δ
+
2 vertices. If the cycle of U contians a maximum-degree vertex, say d
(
v
3
)
=
Δ, then(1)
W
P
(
U
)
≥
n
-
3 when 3
≤
Δ
≤
(
n
-
1
)
/
2, with equality if and only if U
=
U
n
,
4
,
Δ
,
n
-
m
1
-
Δ
-
2
m
1
,
0
,
Δ
-
2,0, where m
1
≤
Δ
-
1 and n
-
m
1
-
Δ
-
2
≥
2 when m
1
≥
2;
(2)
W
P
(
U
)
≥
n
-
4 when Δ
≥
n
/
2, with equality if and only if U
=
U
n
,
4
,
Δ
,
0
Δ
-
2,0
,
m
3
,
0, where m
3
≤
Δ
-
2.Proof.
Assume thatU is an extremal graph with minimum wiener polarity index and properties postulated in the lemma. By Lemma 4 we may assume at first that every hanging tree of U is a path. And so, by Lemma 8, every U
T
[
v
i
] of U is either a path or S
1
,
d
(
v
i
)
-
3
n
i
-
d
(
v
i
)
+
2 with v
i having maximum degree in U
T
[
v
i
] for every i
=
1,2
,
3,4, where n
i
=
U
T
v
i. If n
1
=
1 and n
2
≥
2; we move all the hanging trees on vertex v
2 to v
1 to obtain graph U
1. Since d
U
(
v
3
)
=
Δ
≥
d
U
(
v
4
), by the reasoning as is employed in the first three paragraphs of the proof of Lemma 6, one can deduce from formula (2) that W
P
(
U
1
)
≤
W
P
(
U
). And so, we may assume in what follows that n
1
≥
2.
LetP
i
=
v
i
u
i
1
⋯
u
i
s
i be the longest hanging tree of U on vertex v
i, i
=
1,2
,
3,4. If s
2
≥
1, let U
2
=
U
-
v
2
u
21
+
u
1
s
1
u
21; when s
1
≥
2 we have
(22)
W
P
U
2
-
W
P
U
=
-
1
-
d
U
v
3
-
1
-
d
U
v
1
-
1
-
d
U
v
2
-
1
d
U
u
21
-
1
+
1
+
d
U
2
u
21
-
1
=
2
-
d
U
v
1
-
d
U
v
3
-
d
U
v
2
-
2
d
U
u
21
-
1
≤
2
-
d
U
v
1
-
d
U
v
3
<
0
;
when s
1
=
1 we have
(23)
W
P
U
2
-
W
P
U
=
-
1
-
d
U
v
3
-
1
-
d
U
v
1
-
1
-
d
U
v
2
-
1
d
U
u
21
-
1
+
d
U
v
3
-
1
+
d
U
2
u
21
-
1
=
-
d
U
v
3
-
d
U
v
2
-
2
d
U
u
21
-
1
≤
-
d
U
v
3
<
0
.
These contradictions show that s
2
=
0, namely, d
U
(
v
2
)
=
0. Similarly, we have d
U
(
v
4
)
=
2.
Ifs
3
≥
2, let U
3
=
U
-
u
31
u
32
+
u
1
s
1
u
32, as in above paragraph one can show with ease that W
P
(
U
3
)
<
W
P
(
U
). This contradiction shows that s
3
=
2 and U
T
[
v
3
] is a star with maximum degree Δ
-
2.
Ifd
U
(
v
1
)
+
d
U
(
v
3
)
<
n then
(24)
W
P
U
=
d
U
v
3
-
2
+
d
U
v
1
-
2
+
d
U
v
1
-
1
+
n
-
d
U
v
3
+
d
U
v
1
-
1
=
n
+
d
U
v
1
-
6
≥
n
-
3
,
with the equality holding if and only if the union of hanging trees of U on v
1 is a path. Now, combining this observation with Lemma 4 we deduce that the first statement of Lemma 11 is true since d
U
(
v
1
)
+
d
U
(
v
3
)
<
n implies Δ
≤
(
n
-
1
)
/
2.
Ifd
U
(
v
1
)
+
d
U
(
v
3
)
=
n, which implies Δ
≥
n
/
2, then
(25)
W
P
U
=
d
U
v
1
-
2
+
d
U
v
3
-
2
=
n
-
4
.
And so, the second statement of the lemma is also true.LetΦ
n
,
g
,
Δ denote the set of all such unicyclic graph U
∈
U
n
,
Δ that has following properties: girth g
≥
5; every hanging tree of U is a path; U
T
[
v
1
] is a star S
Δ
-
1 with center v
1; for every edge v
i
v
j in the cycle of U, either U
T
[
v
i
] or U
T
[
v
j
] is a vertex; at most two elements of {
U
T
[
v
i
]
:
i
=
2
,
…
,
g
} is not a vertex; if two elements of {
U
T
[
v
i
]
:
i
=
2
,
…
,
g
} are not vertices then both are paths of length two.Theorem 12.
LetU
∈
U
n
,
Δ be a unicyclic graph with girth g
≥
5. If n
=
Δ
+
g
-
1 then
(26)
W
P
U
≥
n
+
Δ
-
6
=
2
Δ
-
2
=
2
n
-
10
,
i
f
g
=
5
;
n
+
Δ
-
4
=
2
Δ
+
1
=
2
n
-
9
,
i
f
g
=
6
;
n
+
Δ
-
1
=
2
Δ
+
g
-
2
=
2
n
-
g
,
i
f
g
≥
7
.
When Δ
=
3 the equality holds and U
∈
{
U
g
+
2
,
g
,
3,1
1,0
,
…
,
0
}
∪
Φ
g
+
2
,
g
,
3, when Δ
≥
4 the equality holds if and only if U
∈
Φ
Δ
+
g
-
1
,
g
,
Δ.Proof.
Sincen
=
Δ
+
g
-
1, it follows that the maximum-degree vertex is contained in the cycle of U. Now, it is not difficult to see that if the lemma is not true then U
=
U
g
+
2
,
g
,
3,0
1,1
,
0
,
…
,
0 when Δ
=
3, and U
∈
{
U
n
,
g
,
Δ
,
1
1
,
Δ
-
3
,
U
n
,
g
,
Δ
,
0
Δ
-
2,1
} when Δ
≥
4. But, from formula (2) we deduce that W
P
(
U
)
≥
n
-
2 in the first case and W
P
(
U
)
≥
n
-
3 in the second case. And so, the lemma follows.Lemma 13.
LetU
∈
U
n
,
Δ be a unicyclic graph with girth g
≥
5 and n
≥
Δ
+
g vertices. If d
(
v
1
)
=
Δ and every hanging tree of U is a path then
(27)
W
P
U
≥
n
+
Δ
-
5
,
i
f
g
=
5
;
n
+
Δ
-
3
,
i
f
g
=
6
;
n
+
Δ
,
i
f
g
≥
7
,
with equality holding if and only if U
∈
Φ
n
,
g
,
Δ.Proof.
We need to only consider the case whenU has minimum wiener polarity index. By Lemma 4, it suffices to consider the case when U
T
[
v
i
] is a path for every i
≠
1. If U
T
v
i
≠
1
≠
U
T
v
i
+
1 for some edge in the cycle of U, assume without loss of generality that U
T
[
v
i
+
1
] is a path v
i
+
1
u
2
u
3
⋯
u
s and path v
i
w
2
w
3
⋯
w
t is a hanging tree on vertex v
i (it is possible that i
=
1), and let U
1
=
U
-
v
i
+
1
u
2
+
w
t
u
2; from formula (2) one can show with no difficulty that W
P
(
U
1
)
≤
W
P
(
U
)
-
1. This observation shows that for every edge v
i
v
j in the cycle of U, either U
T
[
v
i
] or U
T
[
v
j
] is a vertex.
Suppose thatU
T
[
v
i
], U
T
[
v
j
], and U
T
[
v
k
] are nontrivial, where i
,
j
,
k
≥
2. Let U
T
v
j
=
v
j
x
2
x
3
⋯
x
h and U
2
=
U
-
v
j
x
2
+
v
i
w
t. From formula (2) we can deduce with ease that W
P
(
U
)
-
W
P
(
U
2
)
=
1. This contradiction shows that at most two elements of {
U
T
[
v
i
]
:
i
=
2
,
…
,
g
} are not a vertex. Similarly, one can show that if two elements of {
U
T
[
v
i
]
:
i
=
2
,
…
,
g
} are not vertices then both are paths of length two. Now, the wiener polarity indices of graphs in Φ
n
,
g
,
Δ can be obtained by formula (2) as is listed in the lemma. And so, the lemma follows.Theorem 14.
LetU
∈
U
n
,
Δ be a unicyclic graph with girth g
≥
5. If n
≥
Δ
+
g
+
1 then
(28)
W
P
U
≥
n
-
3
,
w
h
e
n
g
=
5
;
n
-
1
,
w
h
e
n
g
=
6
;
n
+
2
,
w
h
e
n
g
≥
7
,
with equality holding if and only if U
=
U
n
,
g
,
Δ
,
n
-
Δ
-
g
+
1
Δ
-
1,0
,
…
,
0; if n
=
Δ
+
g then
(29)
W
P
U
≥
n
+
Δ
-
5
=
2
Δ
,
w
h
e
n
g
=
5
;
n
+
Δ
-
3
=
2
Δ
+
3
,
w
h
e
n
g
=
6
;
n
+
Δ
=
2
Δ
+
g
,
w
h
e
n
g
≥
7
,
with equlity holding if and only if U
∈
Φ
Δ
+
g
,
g
,
Δ
∪
{
U
Δ
+
g
,
g
,
Δ
,
1
Δ
-
1,0
,
…
,
0
}.Proof.
Assume thatU is an extremal graph with minimum wiener polarity index and the postulated conditions. From Lemmas 3, 4, 5, and 13 we deduce that U
∈
Φ
n
,
g
,
Δ
∪
{
U
n
,
g
,
Δ
,
n
-
Δ
-
g
+
1
Δ
-
1,0
,
0
,
…
,
0
:
n
-
Δ
-
g
+
1
≥
1
}. From formula (2) it follows that if U
=
U
n
,
g
,
Δ
,
n
-
Δ
-
g
+
1
Δ
-
1,0
,
0
,
…
,
0 with n
=
Δ
+
g then
(30)
W
P
U
=
n
+
Δ
-
5
,
when
g
=
5
;
n
+
Δ
-
3
,
when
g
=
6
;
n
+
Δ
,
when
g
≥
7
.
Similarly, if U
∈
{
U
n
,
g
,
Δ
,
n
-
Δ
-
g
+
1
Δ
-
1,0
,
0
,
…
,
0
:
n
≥
Δ
+
g
+
1
} then
(31)
W
P
U
=
n
-
3
,
when
g
=
5
;
n
-
1
,
when
g
=
6
;
n
+
2
,
when
g
≥
7
.
Since Δ
≥
3, comparing these obsevations with the indices of Φ
n
,
g
,
Δ obtained in Lemma 13 we complete the proof of this theorem.Theorem 15.
LetU
∈
U
n
,
Δ be a unicyclic graph with girth g
=
4. If n
≤
2
Δ then W
P
(
U
)
≥
n
-
4 with equality if and only if U
=
U
n
,
4
,
Δ
,
0
Δ
-
2,0
,
m
3
,
0, where m
3
≤
Δ
-
2; if n
≥
2
Δ
+
1 then W
P
(
U
)
≥
n
-
3, with equality if and only if either U
=
U
n
,
4
,
Δ
,
n
-
m
1
-
Δ
-
2
m
1
,
0
,
Δ
-
2,0 with m
1
≤
Δ
-
1 and n
-
m
1
-
Δ
-
2
≥
2 when m
1
≥
2, or U
=
U
n
,
4
,
Δ
,
n
-
m
3
-
Δ
-
3
Δ
-
1,0
,
m
3
,
0 with m
3
≤
Δ
-
2 and n
-
m
3
-
Δ
-
3
≥
2.Proof.
Assume thatU is an extremal graph with minimum wiener polarity index and the postulated conditions. From Lemmas 3, 4, 6, and 11 it follows that U
∈
{
U
n
,
4
,
Δ
,
n
-
m
1
-
Δ
-
2
m
1
,
0
,
Δ
-
2,0
,
U
n
,
4
,
Δ
,
0
Δ
-
2,0
,
m
3
,
0
,
U
n
,
4
,
Δ
,
n
-
m
3
-
Δ
-
3
Δ
-
1,0
,
m
3
,
0
}, where m
1
≤
Δ
-
1 and m
3
≤
Δ
-
2. By formula (2) we have
(32)
W
P
U
n
,
4
,
Δ
,
n
-
m
3
-
Δ
-
3
Δ
-
1,0
,
m
3
,
0
=
n
+
Δ
-
5
,
if
n
-
m
3
-
Δ
-
3
=
1
;
n
-
3
,
if
n
-
m
3
-
Δ
-
3
≥
2
.
Comparing this observation with the results of Lemma 11, we deduce that if n
≤
2
Δ then U
=
U
n
,
4
,
Δ
,
0
Δ
-
2,0
,
m
3
,
0 and W
P
(
U
)
=
n
-
4, where m
3
≤
Δ
-
2; if n
≥
2
Δ
+
1 then W
P
(
U
)
=
n
-
3 and either U
=
U
n
,
4
,
Δ
,
n
-
m
1
-
Δ
-
2
m
1
,
0
,
Δ
-
2,0 with m
1
≤
Δ
-
1 and n
-
m
1
-
Δ
-
2
≥
2 when m
1
≥
2, or U
=
U
n
,
4
,
Δ
,
n
-
m
3
-
Δ
-
3
Δ
-
1,0
,
m
3
,
0 with m
3
≤
Δ
-
2 and n
-
m
3
-
Δ
-
3
≥
2. So, the theorem follows.Theorem 16.
LetU
∈
U
n
,
Δ be a unicyclic graph with girth g
=
3. If n
=
Δ
+
2 then W
P
(
U
)
≥
n
-
4, with equality if and only U
=
U
Δ
+
2,3
,
Δ
,
0
Δ
-
2,1
,
0. If n
≥
Δ
+
3 then W
P
(
U
)
≥
n
-
3, the equality holds if and only if U
∈
{
U
n
,
3
,
Δ
,
n
-
m
2
-
Δ
-
2
Δ
-
1
,
m
2
,
0, U
n
,
3
,
Δ
,
n
-
Δ
-
m
1
-
1
m
1
,
Δ
-
2,0
,
U
n
,
3
,
Δ
,
n
-
m
3
-
Δ
-
2
Δ
-
1
,
m
3
,
U
n
,
3
,
Δ
,
n
-
Δ
-
m
1
′
m
1
′
,
Δ
-
3
} with the following properties:(1)
1
≤
m
1, m
1
′
≤
Δ
-
1, m
2
≤
Δ
-
2 and m
3
≤
Δ
-
3;
(2)
Ifm
1
≥
2 then n
-
m
1
-
Δ
-
1
≥
2; if m
1
′
≥
2 then n
-
m
1
′
-
Δ
≥
2; if m
2
≥
1 then n
-
m
2
-
Δ
-
2
≥
2; if m
3
≥
1 then n
-
m
3
-
Δ
-
2
≥
2.Proof.
Assume thatU is an extremal graph with minimum wiener index and the postulated conditions. If n
=
Δ
+
2 then the maximum-degree vertex is contained in the cycle of U. From Lemma 10 it follows that W
P
(
U
)
=
n
-
4 and U
=
U
Δ
+
2,3
,
Δ
,
0
Δ
-
2,1
,
0.
Now we consider the case whenn
≥
Δ
+
3. By Lemmas 3, 4, 7, and 9 and formula (2), we deduce that W
P
(
U
)
=
n
-
3. Furthermore, if no maximum-degree vertices are contained in the cycle of U then by Lemma 7 we see that U
∈
{
U
n
,
3
,
Δ
,
n
-
m
2
-
Δ
-
2
Δ
-
1
,
m
2
,
0, U
n
,
3
,
Δ
,
n
-
m
3
-
Δ
-
2
Δ
-
1
,
m
3
} with m
2
≤
Δ
-
3, m
3
≤
Δ
-
4 and the properties listed in (2). If the cycle of U contains maximum-degree vertices then by Lemmas 3, 4, and 9 we deduce that U
∈
{
U
n
,
3
,
Δ
,
n
-
Δ
-
m
1
-
1
m
1
,
Δ
-
2,0
,
U
n
,
3
,
Δ
,
n
-
Δ
-
m
1
′
m
1
′
,
Δ
-
3
} with properties listed in (1) and (2). And so, the theorem follows.


## 4. Minimum Index and Extremal Graphs with Prescribed Maximum Degree

This section will determine the minimum wiener polarity index of unicyclic graphs and characterize the extremal graphs.Lemma 17.
LetU
∈
U
n
,
Δ be a unicyclic graph with girth g
≥
5 and n
=
Δ
+
g
-
2 vertices. Then U
=
U
Δ
+
g
-
2
,
g
,
Δ
,
0
Δ
-
2,0
,
…
,
0 and
(33)
W
P
U
=
2
n
-
10
=
2
Δ
-
4
,
i
f
g
=
5
;
2
n
-
9
=
2
Δ
-
1
,
i
f
g
=
6
;
2
n
-
g
=
2
Δ
+
g
-
4
,
i
f
g
≥
7
.Proof.
The lemma is clearly true since, for every given grithg, U
=
U
n
,
g
,
Δ
,
0
Δ
-
2,0
,
…
,
0 is the unique graph that satisfies the postulated conditions.Theorem 18.
LetU
∈
U
n
,
Δ with n
≥
Δ
+
2 and Δ
≥
3.(1)
Ifn
≤
2
Δ then W
P
(
U
)
≥
n
-
4, with equality if and only if U
∈
{
U
Δ
+
2,3
,
Δ
,
0
Δ
-
2,1
,
0
,
U
6,5
,
3,0
1,0
,
0,0
,
0
}
∪
{
U
n
,
4
,
Δ
,
0
Δ
-
2,0
,
m
3
,
0
:
m
3
≤
Δ
-
2
}.
(2)
Ifn
≥
2
Δ
+
1 then W
P
(
U
)
≥
n
-
3, with the equality if and only if U
∈
{
U
7,5
,
3,1
1,0
,
0,0
,
0
}
∪
Φ
7,5
,
3
∪
{
U
n
,
5
,
Δ
,
n
-
Δ
-
4
Δ
-
1,0
,
0,0
,
0
:
n
≥
Δ
+
6
}
∪
{
U
n
,
4
,
Δ
,
n
-
m
3
-
Δ
-
3
Δ
-
1,0
,
m
3
,
0
:
m
3
≤
Δ
-
2
,
n
-
m
3
-
Δ
-
3
≥
2
}
∪
{
U
n
,
4
,
Δ
,
n
-
m
1
-
Δ
-
2
m
1
,
0
,
Δ
-
2,0
:
m
1
≤
Δ
-
1
,
n
-
m
1
-
Δ
-
2
≥
2
w
h
e
n
m
1
≥
2
}
∪
Ψ, where Ψ is the set of graphs listed in the second case of Theorem 16.Proof.
Assume thatU is an extremal graph with minimum wiener polarity index and the conditions postulated in the theorem. By Theorems 12, 14, 15, and 16 and Lemma 17, we see that W
P
(
U
)
=
n
-
4 when n
≤
2
Δ, and W
P
(
U
)
=
n
-
3 when n
≥
2
Δ
+
1. Furthermore, the extremal unicyclic graphs cannot have girth more than five since Δ
≥
3.
Whenn
≤
2
Δ, if g
=
5 then by Theorems 12 and 14 and Lemma 17 we deduce that U
=
U
6,5
,
3,0
1,0
,
0,0
,
0; if g
=
4 then by Theorem 15 we see that U
∈
{
U
n
,
4
,
Δ
,
0
Δ
-
2,0
,
m
3
,
0
:
m
3
≤
Δ
-
2
}; if g
=
3 then from Theorem 16 it follows that U
=
U
Δ
+
2,3
,
Δ
,
0
Δ
-
2,1
,
0.
Now consider the second case whenn
≥
2
Δ
+
1. If g
=
5 and n
=
Δ
+
g
-
2
=
Δ
+
3, since Δ
+
3
=
n
≥
2
Δ
+
1 implies that Δ
≤
2, this contradiction shows that this case contains no extremal graphs. If g
=
5 and n
=
Δ
+
g
-
1
=
Δ
+
4, since Δ
+
4
=
n
≥
2
Δ
+
1 implies Δ
=
3 it follows from Theorem 12 that U
∈
{
U
7,5
,
3,1
1,0
,
0,0
,
0
}
∪
Φ
7,5
,
3. Since n
+
Δ
-
5
≥
n
-
2, it follows form Theorem 14 that there are no extremal graphs with girth g
=
5 and n
=
Δ
+
g
=
Δ
+
5. If g
=
5 and n
≥
Δ
+
g
+
1
=
Δ
+
6, then from Theorem 14 it follows that U
=
U
n
,
5
,
Δ
,
n
-
Δ
-
4
Δ
-
1,0
,
0,0
,
0. For the cases when g
≤
4, the results follows directly from Theorems 15 and 16. And so, the theorem follows.



---

*Source: 316108-2014-11-09.xml*