# Wiener Polarity Index of Cycle-Block Graphs

Authors: Zhen Jia; Fuyi Wei; Yang Wu
Journal: Chinese Journal of Mathematics
 (2014)

---

## Abstract

The Wiener polarity indexW
P of a graph G is the number of unordered pairs of vertices u
,
v of G such that the distance d
G
(
u
,
v
) between u and v is 3. Cycle-block graph is a connected graph in which every block is a cycle. In this paper, we determine the maximum and minimum Wiener polarity index of cycle-block graphs and describe their extremal graphs; the extremal graphs of 4-uniform cactus with respect to Wiener polarity index are also discussed.


---

## Body

## 1. Introduction

LetG
=
(
V
,
E
) be a connected simple graph. The distance d
G
(
u
,
v
) between the vertices u and v of G is defined as the length of a shortest path connecting u and v. N
G
i
(
u
)
=
{
v
∈
V
(
G
)
∣
d
G
(
u
,
v
)
=
i
} is called the ith neighbor set of u. d
(
u
)
=
|
N
G
1
(
u
)
| is called the degree of u. If d
(
u
)
=
1, then u is called a pendant vertex of G. C
l
=
u
1
u
2
⋯
u
l
u
1 denotes a cycle of order l
(
≥
3
). The girth of G, denoted by g, is the length of the shortest cycle of G.A block of the graphG is a maximal 2-connected subgraph of G. A cactus graph is a connected graph in which no edge lies in more than one cycle, such that each block of a cactus graph is either an edge or a cycle. If all blocks of a cactus G are cycles, the graph is defined as cycle-block graph. In this paper, suppose the cycle-block graph consist of n cycles, the length of the cycles may be different. If all blocks of a cactus G are cycles of the same length m, the cactus is m-uniform. A hexagonal cactus is a 6-uniform cactus that every block of the graph is a hexagon. A vertex shared by two or more hexagons is called a cut-vertex. If each hexagon of a hexagonal cactus G has at most two cut-vertices and each cut-vertex is shared by exactly two hexagons, we say that G is a chain hexagonal cactus (see Figure 1(a)). A star cactus is a cactus consisting of n cycles, spliced together in a single vertex u (see Figure 1(b)). A star hexagonal cactus is a star cactus in which every cycle is a hexagon.A chain hexagonal cactus (a) and a star cactus graph (b).
(a)
(b)The Wiener polarity index ofG, denoted by W
P
(
G
), is the number of unordered vertex pairs of distance 3. It was first used in a linear formula to calculate the boiling points t
B of paraffin [1]:
(1)
t
B
=
a
W
(
G
)
+
b
W
P
(
G
)
+
c
,
where a
,
b
,
c are constants for a given isomeric group.The Wiener polarity index became popular recently, and many mathematical properties and its chemical applications were discovered [2–6]. In this line, Du et al. [2] characterized the minimum and maximum Wiener polarity index among all trees of order n, and Deng [3] determined the largest Wiener polarity indices among all chemical trees of order n. M. H. Liu and B. L. Liu [4] determined the first two smallest Wiener polarity indices among all unicyclic graphs of order n. Hou et al. [5] determined the maximum Wiener polarity index of unicyclic graphs. Behmarama et al. [6] computed the Wiener polarity index of hexagonal cacti. To know more about cactus graph one can research [7, 8].In this paper, we discuss the extremal graphs of Wiener polarity index of cycle-block graphs withg
≥
5 and 4-uniform cactus.


## 2. The Extremal Graphs of Wiener Polarity Index of Cycle-Block Graphs withg
≥
5

In this section, we characterize the maximum and minimum Wiener polarity index of the cycle-block graphs withg
≥
5.Suppose thatG
1 and G
2 are two connected graphs. The graph obtained by identifying a chosen vertex of G
1 and another of G
2 is called the coalescence of G
1 and G
2, denoted by G
1
∘
G
2. The vertex identifying G
1 and G
2 is called the coalescence vertex. The cycle-block graph which consist of n cycles C
1
,
C
2
,
…
,
C
n can be seen as the coalescence of cycles by n
-
1 times, G
≅
C
1
∘
C
2
∘
⋯
∘
C
n.Lemma 1.
LetG
1 and G
2 be two connected graphs; suppose that v
0 is the coalescence vertex of G
1
∘
G
2. Then W
P
(
G
1
∘
G
2
)
=
W
P
(
G
1
)
+
W
P
(
G
2
)
+
∑
k
=
1
2
‍
|
N
G
1
k
(
v
0
)
|
|
N
G
2
3
-
k
(
v
0
)
|.Proof.
Suppose thatu
,
v
∈
V
(
G
1
∘
G
2
) and d
G
1
∘
G
2
(
u
,
v
)
=
3. Then,
(2)
|
{
(
u
,
v
)
∣
d
G
1
∘
G
2
(
u
,
v
)
=
3
,
u
,
v
∈
V
(
G
i
)
}
|
=
W
P
(
G
i
)
,
h
h
h
h
h
h
h
h
h
h
i
=
1,2
,
|
{
(
u
,
v
)
∣
d
G
1
∘
G
2
(
u
,
v
)
=
3
,
u
∈
V
(
G
1
)
,
v
∈
V
(
G
2
)
}
|
=
∑
k
=
1
2
‍
|
N
G
1
k
(
v
0
)
|
|
N
G
2
3
-
k
(
v
0
)
|
.
By the definition of Wiener polarity index, the result holds.Theorem 2.
LetG be a cycle-block graph with g
≥
5 and let G be consisting of n cycles C
1
,
C
2
,
…
,
C
n. Then
(3)
W
P
(
G
)
≤
∑
i
=
1
n
‍
W
P
(
C
i
)
+
8
(
n
2
)
;
the equality holds if and only if G
≅
G
*, where G
* is a star cactus graph.Proof.
LetG be a cycle-block graph with g
≥
5. Here we apply induction to n.
Whenk
=
2, the graph is determined uniquely. By Lemma 1 and elementary computation, we have W
P
(
G
)
=
∑
i
=
1
2
‍
W
P
(
C
i
)
+
8.
Whenk
=
3, there are three cycles C
1, C
2, and C
3. The graph G is obtained from C
1
∘
C
2 by attaching a new cycle C
3 to C
1
∘
C
2. There are three ways to attach the cycle C
3. Here we suppose that v
0 is the coalescence vertex of C
1
∘
C
2 and v
1 is the new coalescence vertex of C
1
∘
C
2
∘
C
3.
By Lemma1 and elementary computation, we have
(4)
W
P
(
G
)
=
{
∑
i
=
1
3
‍
W
P
(
C
i
)
+
8
(
3
2
)
,
d
(
v
0
,
v
1
)
=
0
,
∑
i
=
1
3
‍
W
P
(
C
i
)
+
20
,
d
(
v
0
,
v
1
)
=
1
,
∑
i
=
1
3
‍
W
P
(
C
i
)
+
16
,
d
(
v
0
,
v
1
)
≥
2
,
where d
(
v
0
,
v
1
)
=
0 implies that G is the star cactus graph. From the result of the three cases, it holds for the result.
Now suppose that the assertion holds fork
=
n
-
1. Next we prove that the result holds for k
=
n.
Suppose thatv
0 is the coalescence vertex of C
1
∘
C
2
∘
⋯
∘
C
n
-
1 and v
1 is the coalescence vertex of C
1
∘
C
2
∘
⋯
∘
C
n. Three cases occur
(5)
W
P
(
G
)
=
{
∑
i
=
1
n
W
P
(
C
i
)
+
8
(
n
2
)
,
d
(
v
0
,
v
1
)
=
0
,
∑
i
=
1
n
W
P
(
C
i
)
+
8
(
n
-
1
2
)
+
4
n
,
d
(
v
0
,
v
1
)
=
1
,
∑
i
=
1
n
W
P
(
C
i
)
+
8
(
n
-
1
2
)
+
8
,
d
(
v
0
,
v
1
)
≥
2
,
where d
(
v
0
,
v
1
)
=
0; it implies that G is the star cactus graph. Obviously, the star cactus graph has the maximum Wiener polarity index of cycle-block graphs with g
≥
5. This completes the proof.Let𝔾 be a graph set that consists of the cycle-block graphs of n cycles with n
-
1 cut-vertices and the distance between any cut-vertices being greater than 1. By a similar method with Theorem 2, we have Theorem 3; the proof is in the Appendix.Theorem 3.
LetG be a cycle-block graph with g
≥
5 and let G be consisting of n cycles C
1
,
C
2
,
…
,
C
n. Then
(6)
W
P
(
G
)
≥
∑
i
=
1
n
‍
W
P
(
C
i
)
+
8
(
n
-
1
)
;
the equality holds if and only if G
∈
𝔾.Remark 4.
By Theorems2 and 3, we know that the cycle-block graph with maximum Wiener polarity index is determined uniquely while the cycle-block graph with minimum Wiener polarity index is not.
For some types of hexagonal cacti which represent common chemical structures, as an extension, we obtain the6-uniform cactus with the maximum and minimum Wiener polarity index.Corollary 5.
LetG be 6-uniform cactus with n hexagons. Then 11
n
-
8
≤
W
P
(
G
)
≤
4
n
2
-
n; the first equality holds if and only if there are n
-
1 different cut-vertices in G and distance between any two vertices is greater than 1; the second equality holds if and only if G is a star hexagonal cactus graph.


## 3. The Extremal Graphs of Wiener Polarity Index of 4-Uniform Cactus

The case of4-uniform cactus’ extremal graphs is different from the cycle-block graphs with g
≥
5 and more complex. Let Q
n
(
i
,
j
,
t
,
w
) be a graph obtained from a quadrilateral C
4
=
v
1
v
2
v
3
v
4
v
1 by attaching i, j, t, and w quadrilaterals to vertices v
1, v
2, v
3, and v
4, respectively, where i
+
j
+
t
+
w
+
1
=
n (see Figure 2).Figure 2
The graph ofQ
n
(
i
,
j
,
k
,
ω
).Theorem 6.
Suppose thatG is 4-uniform with n
(
≥
2
) quadrilaterals. Then
(7)
W
P
(
G
)
≤
2
n
2
-
2
n
;
the equality holds if and only if G
≅
Q
n
(
i
,
j
,
0,0
), where i
≥
0
,
j
=
n
-
1
-
i.Proof.
We apply induction ton.
Whenk
=
2, G is unique. By Lemma 1, we have W
P
(
G
)
=
4; the result follows.
Whenk
=
3, we have
(8)
W
P
(
G
)
=
{
12
,
G
≅
Q
3
(
2,0
,
0,0
)
,
12
,
G
≅
Q
3
(
1,1
,
0,0
)
,
8
,
G
≅
Q
3
(
1,0
,
1,0
)
;
the result holds.
Suppose that the result holds fork
=
n
-
1. When k
=
n, there is a new quadrilateral to be attached to Q
n
-
1
(
i
,
j
,
0,0
), where j
=
n
-
2
-
i
,
i
≥
0. Without loss of generality, suppose that i
>
0; there are two cases to be discussed concerning of the variable parameters of j.
C
ase
1
(
j
=
0
)
. It is a star quadrilateral cactus. Three new graphs Q
n
(
n
-
1,0
,
0,0
), Q
n
(
n
-
2,1
,
0,0
), and Q
n
(
n
-
2,0
,
1,0
) are obtained by three different ways to attach a quadrilateral to Q
n
-
1
(
n
-
2,0
,
0,0
).
By elementary computation and Lemma1, we have
(9)
W
P
(
G
)
=
{
2
(
n
-
1
)
2
-
2
(
n
-
1
)
+
2
×
(
n
-
1
)
+
1
×
2
(
n
-
1
)
,
2
(
n
-
1
)
2
-
2
(
n
-
1
)
+
2
×
(
2
(
n
-
2
)
+
1
)
+
1
×
2
,
2
(
n
-
1
)
2
-
2
(
n
-
1
)
+
2
×
1
+
1
×
2
,
=
{
2
n
2
-
2
n
,
G
≅
Q
n
(
n
-
1,0
,
0,0
)
,
2
n
2
-
2
n
,
G
≅
Q
n
(
n
-
2,1
,
0,0
)
,
2
n
2
-
6
n
+
8
,
G
≅
Q
n
(
n
-
2,0
,
1,0
)
.
For these three subcases, the result follows.
Case
2
(
j
>
0
)
. There are also three subcases to attach a new quadrilateral to Q
n
-
1
(
i
,
j
,
0,0
).
Subcase
1.
G
≅
Q
n
(
i
+
1
,
j
,
0,0
) or G
≅
Q
n
(
i
,
j
+
1,0
,
0
).
We only prove the caseG
≅
Q
n
(
i
+
1
,
j
,
0,0
). G
≅
Q
n
(
i
,
j
+
1,0
,
0
) can be proved similarly. By elementary computation and Lemma 1, we have
(10)
W
P
(
Q
n
(
i
+
1
,
j
,
0,0
)
)
=
2
(
n
-
1
)
2
-
2
(
n
-
1
)
+
2
×
(
i
+
1
+
2
j
)
+
1
×
2
(
i
+
1
)
=
2
n
2
-
2
n
.
Subcase
2.
G
≅
Q
n
(
i
,
j
,
1,0
) or G
≅
Q
n
(
i
,
j
,
0,1
).
WhenG
≅
Q
n
(
i
,
j
,
1,0
), by elementary computation and Lemma 1, we have
(11)
W
P
(
Q
n
(
i
,
j
,
1,0
)
)
=
2
(
n
-
1
)
2
-
2
(
n
-
1
)
+
2
×
(
2
j
+
1
)
+
1
×
2
=
2
n
2
-
6
n
+
4
j
+
8
.
Similarly, W
P
(
Q
n
(
i
,
j
,
0,1
)
)
=
2
n
2
-
6
n
+
4
i
+
8.
Subcase
3. The new quadrilateral attach to one of the i or j quadrilaterals and create a new cut-vertex different from v
1 and v
2.
When a new quadrilateral is attached to one of thej quadrilaterals. The distance between the new cut-vertex and its nearest cut-vertex is 1. By elementary computation and Lemma 1, we have
(12)
W
P
(
G
)
=
2
(
n
-
1
)
2
-
2
(
n
-
1
)
+
2
×
(
1
+
2
j
)
+
1
×
2
=
2
n
2
-
6
n
+
4
j
+
8
.
Analogously, when the new quadrilateral is attached to one of the i quadrilaterals, we have W
P
(
G
)
=
2
n
2
-
6
n
+
4
i
+
8.
When the distance between the new cut-vertex and its nearest cut-vertex is 2. By elementary computation and Lemma1, we have
(13)
W
P
(
G
)
=
2
(
n
-
1
)
2
-
2
(
n
-
1
)
+
2
×
1
+
1
×
2
=
2
n
2
-
6
n
+
8
.
By the discussion of Case 2 above, for i
>
0
,
j
>
0, it is easy to verify that 2
n
2
-
2
n
>
max
⁡
{
2
n
2
-
6
n
+
4
i
+
12,2
n
2
-
6
n
+
4
j
+
12,2
n
2
-
6
n
+
8
}. This completes the proof.With the analogous method with Theorem3, we can deduce the minimum Wiener polarity index of 4-uniform (see the proof of the Appendix).Theorem 7.
LetG be 4-uniform with n quadrilaterals. Then
(14)
W
P
(
G
)
≥
4
(
n
-
1
)
;
the equality holds if and only if  G
≅
G
′, where G
′ is a chain quadrilateral cactus with the distance between the cut-vertices being at least 2 (see Figure 3).Figure 3
The graph ofG
′.Remark 8.
From Theorems6 and 7, we can conclude that the extremal 4-uniform with the maximum Wiener polarity index is not unique, but the minimum case is unique and different from the case of cycle-block graphs with g
≥
5. For the case of extremal cycle-block with g
≥
3 of Wiener polarity index is very complex, we do not discuss it here.



---

*Source: 476705-2014-02-27.xml*