# The Wiener Index of Circulant Graphs

Authors: Houqing Zhou
Journal: Journal of Chemistry
 (2014)

---

## Abstract

Circulant graphs are an important class of interconnection networks in parallel and distributed computing. In this paper, we discuss the relation of the Wiener index and the Harary index of circulant graphs and the largest eigenvalues of distance matrix and reciprocal distance matrix of circulants. We obtain the following consequence:W
/
λ
=
H
/
μ; 2
W
/
n
=
λ; 2
H
/
n
=
μ, where W, H denote the Wiener index and the Harary index and λ, μ denote the largest eigenvalues of distance matrix and reciprocal distance matrix of circulant graphs, respectively. Moreover we also discuss the Wiener index of nonregular graphs with cut edges.


---

## Body

## 1. Introduction

A circulant graph is a graph whose adjacency matrix (with respect to a suitable vertex indexing) can be constructed from its first row by a process of continued rotation of entries. The interest of circulant graphs in graph theory and applications has grown during the last two decades; they appeared in coding theory, VLSI design, Ramsey theory, and other areas. Recently there is vast research on the interconnection schemes based on circulant topology. Circulant graphs represent an important class of interconnection networks in parallel and distributed computing [1].We consider simple graphs. LetG be a connected graph with the vertex-set V
(
G
)
=
{
v
1
,
v
2
,
…
,
v
n
}. The distance matrix D of G is an n
×
n matrix (
D
i
j
) such that D
i
j is just the distance (i.e., the number of edges of a shortest path) between the vertices v
i and v
j in G. The reciprocal distance matrix D
i
j
r of G is also called the Harary matrix [2].Forv
i
∈
V
(
G
), N
G
(
v
i
) denotes the set of its neighbors in G. Let λ
(
G
) and μ
(
G
) be, respectively, the maximum eigenvalues of D and D
r; the distance spectral radius of G is the largest D-eigenvalue λ
(
G
). Ivanciuc et al. [3] proposed to use the maximum eigenvalues of distance-based matrices as structural descriptors; they have shown that λ
(
G
) and μ
(
G
) are able to produce fair QSPR models for the boiling points, molar heat capacities, vaporization enthalpies, refractive indices, and densities forC
6–C
10  alkanes.Recall the Hosoya definition of the Wiener index [4] and the Harary index:
(1)
W
(
G
)
=
∑
i
<
j
‍
D
i
j
,
H
(
G
)
=
∑
i
<
j
‍
D
i
j
r
.Since the distance matrix and related matrices, based on graph-theoretical distance, are rich sources of many graph invariants (topological indices) that have been found to be used in structure-property-activity modeling [5], it is of interest to study spectra and polynomials of these matrices.The Harary index,H
=
H
(
G
), of a molecular graph G with n vertices is based on the concept of reciprocal distance and is defined, in parallel with the Wiener index, as the half-sum of the off-diagonal elements of the reciprocal molecular distance matrix D
i
j
r
=
D
r
(
G
):
(2)
H
=
1
2
∑
i
=
1
N
‍
∑
j
=
1
N
‍
[
D
r
]
i
j
.The reciprocal distance matrixD
i
j
r can be simply obtained by replacing all off-diagonal elements of the distance matrix D
i
j by their reciprocals:
(3)
D
i
j
r
=
1
D
i
j
.
It should be noted that diagonal elements (
D
r
)
i
i are all equal to zero by definition. This matrix was first mentioned by Balaban et al. [6]. The maximum eigenvalues of various matrices have recently attracted attention of mathematical chemists [6–8].The Harary index and the related indices such as its extension to heterosystems [7] and the hyper-Harary index [8] have shown a modest success in structure-property correlations [9], but the use of these indices in combination with other descriptors appears to be very efficacious in improving the QSPR (quantitative structure-property relationship) models.The paper is organized as follows. In Section2 we bring forward an interesting phenomenon. In Section 3, we analyze the cause of this phenomenon to emerge; we report our results for the maximum eigenvalues of the Wiener matrix and the Harary matrix of r-circulant graphs. Finally, in Section 4, we discuss the Wiener index of nonregular graphs.


## 2. An Interesting Phenomenon

Recall that, for a positive integern and set S
⊆
{
0,1
,
2
,
…
,
n
-
1
}, the circulant graph G
(
n
,
S
) is the graph with n vertices, labeled with integers modulo n, such that each vertex i is adjacent to S other vertices {
i
+
s
(
mod
⁡
n
)
∣
s
∈
S
}. The set S is called a symbol of G
(
n
,
S
). As we will consider only undirected graphs without loops, we assume that 0
∉
S and s
∈
S if and only if n
-
s
∈
S, and therefore the vertex i is adjacent to vertices i
±
s
(
mod
⁡
n
) for each s
∈
S. In other words, a graph is circulant if it is Cayley graph on the circulant group; that is, its adjacency matrix is circulant.For any circulant graphG, it is a regular graph. A r-circulant graph is called regular of degree (or valency) r, when every vertex has precisely r neighbors. Let d denote the diameter of G; then d is less than the number of distinct eigenvalues of the adjacency matrix of G (see [10]).Now, consider 4-circulant graphs with6,7
,
…
,
18 vertices, respectively. By a straightforward mathematical calculation, we obtain some data on the Wiener index: W, the Harary index: H, and the eigenvalues: λ, μ of the Wiener matrix and the Harary matrix as follows in Table 1.Table 1
n
W
H
d
λ
μ
W
/
H
λ
/
μ
2
W
/
n
2
H
/
n
6
18
13.5
2
6
4.5
4/3
4/3
6
4.5
7
28
17.5
2
8
5
8/5
8/5
8
5
8
40
22
2
10
5.5
20/11
20/11
10
5.5
9
54
27
2
12
6
2
2
12
6
10
75
95/3
3
15
19/3
45/19
45/19
15
19/3
11
99
110/3
3
18
20/3
27/10
27/10
18
20/3
12
126
42
3
21
7
3
3
21
7
13
156
143/3
3
24
22/3
36/11
36/11
24
22/3
14
196
637/12
4
28
91/12
48/13
48/13
28
91/12
15
240
235/4
4
32
47/6
192/47
192/47
32
47/6
16
288
194/3
4
36
97/12
432/97
432/97
36
97/12
17
340
425/6
4
40
25/3
24/5
24/5
40
25/3
18
405
384/5
5
45
128/15
675/128
675/128
45
128/15From Table1, it is easy to observe that W
/
H and λ
/
μ are equal. Moreover, we have 2
W
/
n
=
λ and 2
H
/
n
=
μ.We again observe Table2.Table 2
Graph
S
W
H
λ
μ
W
/
H
λ
/
μ
2
W
/
n
2
H
/
n
G(10, S)
{
1,5
,
9
}
85
85/3
17
17/3
3
3
17
17/3
G(10, S)
{
1,2
,
8,9
}
75
95/3
15
19/3
45/19
45/19
15
19/3
G(10, S)
{
1,2
,
5,8
,
9
}
65
35
13
7
13/7
13/7
13
7
G(10, S)
{
1,2
,
3,7
,
8,9
}
60
75/2
12
15/2
8/5
8/5
12
15/2
G(10, S)
{
1,2
,
3,5
,
7,8
,
9
}
55
40
11
8
11/8
11/8
11
8
G(10, S)
{
1,2
,
3,4
,
6,7
,
8,9
}
50
85/2
10
17/2
20/17
20/17
10
17/2From Table2, we also obtain the same results previously when the number of vertices is fixed in G
(
n
,
S
).Why does this phenomenon occur? We will be interested in trying to explain something about this phenomenon. To prove our result, we need a few more lemmas.Lemma 1 (see [11]).
LetB
=
(
B
i
j
) be an n
×
n nonnegative irreducible symmetric matrix (
n
≥
2
) with row sums B
1
,
B
2
,
…
,
B
n. If ρ
(
B
) is the maximum eigenvalue of B, then
(4)
∑
i
=
1
n
B
i
2
n
≤
ρ
(
B
)
≤
max
⁡
1
≤
i
≤
n
∑
j
=
1
n
‍
B
i
j
B
j
B
i
,
with either equality if and only if B
1
=
B
2
=
⋯
=
B
n or there is a permutation matrix Q such that
(5)
Q
T
B
Q
=
(
0
C
C
T
0
)
,
where all the row sums of C are equal.Lemma 2 (see [12]).
LetG be a r-regular graph of order n. If r
,
λ
2
,
…
,
λ
n are the adjacency eigenvalues of G, then its D-eigenvalues are 2
n
-
r
-
2 and -
(
λ
i
+
2
)
,
i
=
2,3
,
…
,
n, where D-eigenvalues denote the eigenvalues of the distance matrix D
(
G
).Lemma 3 (see [13]).
LetG be a r-circulant graph on n vertices and the Wiener index W of  G; then the following equality holds:
(6)
W
≥
n
·
(
n
-
1
)
-
|
E
|
,
where |
E
| denotes the number of edges.Lemma 4 (see [14]).
LetC
1 be a component of G
-
u and v
1
,
v
2
,
…
,
v
k
(
1
≤
k
≤
deg
⁡
G
(
u
)
-
deg
⁡
C
1
(
u
)
)
∈
{
N
G
(
u
)
∖
N
C
1
(
u
)
}. If N
C
1
(
u
)
∖
{
v
}
=
N
C
1
(
v
), where v is adjacent to u in C
1, let G
′ be obtained by removing an edge u
v
s of G and add a new edge v
v
s
(
1
≤
s
≤
k
). For all 1
≤
s
≤
k, if a vertex w
∈
V
(
G
)
∖
V
(
C
1
)
∪
{
u
} satisfies dist
⁡
G
(
w
,
v
s
)
<
dist
⁡
G
′
(
w
,
v
s
), then λ
(
G
)
<
λ
(
G
′
), where dist
⁡
G
(
u
,
v
) denotes the distance between a pair of vertices u
,
v in G.


## 3. Main Results

In this section, we will prove the following two theorems.Theorem 5.
LetG be a r-circulant graph on n
(
n
≥
4
) vertices; then the following equality holds:
(7)
W
(
G
)
H
(
G
)
=
λ
(
G
)
μ
(
G
)
.Proof.
Obviously,D and D
r are irreducible for n
≥
4. By Lemma 1, we have
(8)
∑
i
=
1
n
D
i
2
n
≤
λ
(
G
)
≤
max
⁡
1
≤
i
≤
n
∑
j
=
1
n
‍
D
i
j
D
j
D
i
,
∑
i
=
1
n
(
D
r
)
i
2
n
≤
μ
(
G
)
≤
max
⁡
1
≤
i
≤
n
∑
j
=
1
n
‍
(
D
r
)
i
j
(
D
r
)
j
(
D
r
)
i
.
Note that G is a regular graph of degree r; hence all the row sums of D and D
r are equal, respectively; that is, D
1
=
D
2
=
⋯
=
D
n, D
1
r
=
D
2
r
=
⋯
=
D
n
r; then we have
(9)
λ
(
G
)
=
∑
i
=
1
n
D
i
2
n
,
μ
(
G
)
=
∑
i
=
1
n
(
D
r
)
i
2
n
.
On the other hand, according to definitions of the Wiener index and the Harary index, we have
(10)
W
(
G
)
H
(
G
)
=
∑
i
<
j
‍
D
i
j
∑
i
<
j
‍
(
D
r
)
i
j
=
∑
i
=
1
n
D
i
2
∑
i
=
1
n
(
D
r
)
i
2
.
Thus we obtain
(11)
W
(
G
)
H
(
G
)
=
λ
(
G
)
μ
(
G
)
.Theorem 6.
LetG be a r-circulant graph on n vertices; then its Wiener index W and Harary index H listed below have the following relationship:
(12)
2
W
n
=
λ
,
2
H
n
=
μ
.Proof.
Since ar-circulant graph is a r-regular graph, applying Lemma 2, we get its maximum distance matrix eigenvalue:
(13)
λ
=
2
(
n
-
1
)
-
r
.
For r-regular graphs G
=
(
V
,
E
) on n vertices the following equality holds:
(14)
n
·
r
=
2
|
E
|
,
and we denote by |
E
| the number of edges of G. According to (6) and (14) we have
(15)
W
≥
n
(
n
-
1
)
-
n
r
2
.
That is, 2
W
≥
2
n
(
n
-
1
)
-
n
r. By (13) and (15), we have
(16)
2
W
n
≥
λ
.
On the other hand, Indulal proved the following fact in [15].
Fact.Let G be a graph with Wiener index W. Then λ
≥
2
W
/
n and the equality holds if and only if G is distance regular.
Then, from (16) and the previous fact, we have 2
W
/
n
=
λ.
By equality (11), we obtain 2
H
/
n
=
μ. This completes the proof of the theorem.


## 4. Nonregular Graphs

As we just said, for a regular, those conclusions above hold. But for nonregular graph, it is not easy to tell whether or not the conclusions also hold.For arbitrary tree onn vertices, It is proved that (see [16])
(17)
(
n
-
1
)
2
≤
W
(
T
n
)
≤
(
n
+
1
3
)
,
with equality on the left if and only if  T
n
≅
S
1
,
n
-
1 and equality on the right if and only if  T
n
≅
P
n, where P
n is the path and S
1
,
n
-
1 is the star on n vertices.Without loss of generality, we now discuss the Wiener index of graphK
n
k; it is obtained by joining k pendent edges to a vertex of complete graph K
n
-
k.It is well known that the Wiener index ofG has a direct proportion with the distance spectral radius of G as vertices fixed; that is, the distance spectral radius of G is strictly increasing with the Wiener index increasing [15]. Then we show the following theorem.Theorem 7.
LetG be a simple connected graph on n
(
n
≥
4
) vertices and k cut edges; then W
(
G
)
≥
W
(
K
n
k
).Proof.
We will use the above well known fact to proveλ
(
G
)
≥
λ
(
K
n
k
), with equality if and only if G
≅
K
n
k.
LetE
′
=
(
e
1
,
e
2
,
…
,
e
k
) be set of cut edges; assume any block of G
-
E
′ has a clique. If k
=
0, then G
≅
K
n
k, and the proposition holds.
Now suppose thatk
≥
1; let K
a
0
,
K
a
1
,
…
,
K
a
k denote the components of G
-
E
′, respectively, where a
0
+
a
1
+
⋯
+
a
k
=
n.
LetV
a
i
=
{
v
∈
K
a
i
,
v
is
a
endpoint
of
a
cut
edge
}.
Claim
1 (
|
V
a
i
|
=
1
,
0
≤
i
≤
k
). In fact, if 0
≤
i
≤
k, such that |
V
a
i
|
>
1, let u
,
v
∈
V
a
i, and v
v
j
,
u
v
h
∈
E
′. Let G
′
=
G
-
v
v
j
-
u
v
h. Obviously, G
′ is a disconnected graph on n vertices and k cut edges, and dist
⁡
G
′
(
v
h
,
v
j
)
<
dist
⁡
G
(
v
h
,
v
j
). Due to N
k
a
i
(
u
)
∖
{
v
}
=
N
k
a
i
(
v
)
∖
{
u
} in G
′ by Lemma 4, we have λ
(
G
′
)
<
λ
(
G
), and then we reach a contradiction.
Without loss of generality, assumeV
a
i
=
{
v
i
}
,
0
≤
i
≤
k.
Claim
2. If v
s is adjacent to v
t, 0
≤
s
,
t
≤
k, then d
(
v
s
)
=
1 or d
(
v
t
)
=
1.
In fact, ifd
(
v
s
)
≥
2 and d
(
v
t
)
≥
2.
LetC
1
,
C
2 denote two components containing v
s
,
v
t in G
-
v
s
v
t, respectively, and u
∈
N
(
v
s
)
∖
{
v
t
}
=
{
v
k
+
1
,
v
k
+
2
,
…
,
v
k
+
r
}.
LetG
′
=
G
-
v
s
v
k
+
1
-
⋯
-
v
s
v
k
+
r
+
v
t
v
k
+
1
+
⋯
+
v
t
v
k
+
r. Then G
′ still is a connected graph with n vertices and k cut edges, and dist
⁡
G
′
(
u
,
v
k
+
i
)
<
dist
⁡
G
(
u
,
v
k
+
i
)
(
1
≤
i
≤
r
), where v
s
v
t is a pendent edge in G
′. Using Lemma 4, we have λ
(
G
′
)
<
λ
(
G
), and this leads to a contradiction.
SinceG is connected, according to Claims 1 and 2, we obtain G
≅
K
n
k. Hence we have W
(
G
)
≥
W
(
K
n
k
).
This completes the proof of the theorem.



---

*Source: 742121-2014-04-09.xml*