# The Global Cyclicity Index of Benzenoid Chains

Authors: Yujun Yang; Yan Wang; Yi Li
Journal: Journal of Chemistry
 (2013)

---

## Abstract

The resistance distanceΩG(i,j) between vertices  i and j of a connected (molecular) graph G is computed as the effective resistance between nodes i and j in the
corresponding network constructed from G by replacing each edge of G with a unit
resistor. The conductance excess between any i and j of G is the difference between 1/ΩG(i,j) and the reciprocal of the distance between  i and j. The global cyclicity index of G is defined as the sum of conductance excesses between all pairs of adjacent
vertices. In this paper, by computing resistance distances between pairs of adjacent
vertices in linear polyacenes, an explicit formula for the global cyclicity index of a
benzenoid chain is obtained in terms of its number of hexagons.


---

## Body

## 1. Introduction

As the number of possible chemical compounds is so big, their huge part will never be experimentally tested. For this reason, there is a need for mathematical modeling and analysis of certain classes of compounds. To this end, many topological indices are defined and applied in the modeling of chemical and pharmacological properties of molecules. In the present work, we will take a new molecular cyclicity measure into consideration.There are different possible measures of “cyclicity” of a molecular graphG=(V(G),E(G)). One simple such traditional fundamental measure is the cyclomatic number μ(G) (also called the first Betti number, the nullity, or the cycle rank) which is defined for a connected graph G with n vertices and m edges as
(1)μ(G)=m-n+1.
Motivated from electrical network theory, Klein and Ivanciuc proposed a new cyclicity measure. This new cyclicity measure is established on the basis of the novel concept of resistance distance [1–7]. As an intrinsic graph metric, the resistance distance  ΩG(i,j) between vertices i and j of a connected (molecular) graph G is computed as the effective resistance between nodes i and j in the corresponding network constructed from G by replacing each edge of G with a unit resistor. Comparing to the traditional (shortest path) distance dG(i,j) between i and j, it is well known that ΩG(i,j) equals the length dG(i,j) of the shortest path between i and j if there is a unique single path between i and j, while if there is more than one path, then ΩG(i,j) is strictly less than dG(i,j). Thence, the conductance excess  σG(i,j)-1/dG(i,j) indicates in some manner the presence of cyclicity in the portion of the graph interconnecting i and j, where σG(i,j)=1/ΩG(i,j) is known as the effective conductance between i and j. To measure the cyclicity of a graph G, Klein and Ivanciuc [8] proposed the global cyclicity index  C(G) as
(2)C(G)=∑i~j‍[σG(i,j)-1dG(i,j)],
where i~j means that i and  j are adjacent and the sum is over all edges of G. Since dG(i,j)=1 for i~j, C(G) can also be written as
(3)C(G)=∑i~j‍[σG(i,j)-1]=∑i~j‍σG(i,j)-|E(G)|.As a new measure of cyclicity of graphs, the global cyclicity index has less degeneracy than the standard cyclomatic number and has some intuitively appealing features. Since the idea of cyclicity is related to measures of connectivity or complexity [9] and characterization of “cyclicity” is an aspect of key importance in the study of molecular graphs [10, 11], it is worth studying the global cyclicity index from both mathematical and chemical points of view.Abenzenoid system is a 1-connected collection of congruent regular hexagons arranged in the plane in such a way that any two hexagons having a common point intersect in a whole edge. The vertices lying on the border of the unbounded face of a benzenoid system are called external; other vertices, if present, are called internal. A benzenoid system without internal vertices is called catacondensed. If no hexagon in a catacondensed benzenoid is adjacent to three other hexagons, we say that the benzenoid is a benzenoid chain. If a benzenoid chain has no turn hexagons, then it is called a linear polyacene.In [8], Klein and Ivanciuc established a number of theorems for the global cyclicity index of graphs (even not connected). In [12], one of the present authors obtained bounds for the global cyclicity index of fullerene graphs. In [13], one of the present authors also obtained some further results on the global cyclicity number, including the strictly monotone increasing property, some lower and upper bounds, and some Nordhaus-Gaddum-type results, a relationship between C(G) and the cyclomatic number μ(G). In this paper, by computing resistance distances between pairs of adjacent vertices in linear polyacenes, an explicit formula for the global cyclicity index of benzenoid chains is obtained in terms of the number of hexagons.


## 2. Results

### 2.1. Resistance Distances between Adjacent Vertices in Linear Polyacenes

In this subsection, we will compute resistance distances between pairs of adjacent vertices in linear polyacenes. Denote byLn the linear polyacene with n hexagons. For convenience, we label the vertices of Ln as depicted in Figure 1.A benzenoid chain withn hexagons (a) and the linear polyacene Ln (b).
(a)
(b)To compute resistance distances between pairs of adjacent vertices inLn, we need to employ the classical result of computing resistance distances in terms of spanning trees and spanning bi-trees. A spanning tree (resp., forest) of a connected graph G is a subgraph that contains all the vertices and is a tree (resp., forest). A spanning bi-tree of a connected graph is defined as a spanning forest of the graph with exactly two components. A spanning bi-tree is said to separate vertices i and j if the vertices i and j are in distinct components of the bi-tree. For a connected graph G and for any two vertices i,j∈V(G), we denote by t(G) and t(G;i,j) the number of spanning trees of G and the number of spanning bi-trees of G separating i and j, respectively. Then resistance distances can be computed as given in the following Lemma.Lemma 1 (see [14]).
LetG be a connected graph. Then the resistance distance between any two vertices i and j in G can be computed as
(4)ΩG(i,j)=t(G;i,j)t(G).Now suppose thati and j are adjacent in G, and let e be an edge connecting them. If T is a spanning tree that contains e, then by the deletion of e from T we could obtain a spanning bi-tree F separating i and j. Conversely, if F is a spanning bi-tree separating i and j, then by adding an new edge e connecting i and j to F we could obtain a spanning tree of G. So, the number of spanning trees containing e is equal to the number of spanning bi-trees separating i and j. While, on the other hand, the number of spanning trees of G that contain e is equal to the number of spanning trees of the graph G/e, where G/e denotes the graph obtained from G by contracting e, that is, deleting e and then identifying two end vertices of e. Thus, as a consequence of Lemma 1, we have the following result.Lemma 2.
LetG be a connected graph with e=ij∈E(G). Then
(5)ΩG(i,j)=t(G/e)t(G).In the enumeration of spanning trees of graphs, there is a famous recursion formula, known as the deletion-contraction recurrence. As stated in the following lemma, the recursion formula is applicable tomultiple graphs (i.e., graphs with multiple edges).Lemma 3.
LetG be a multiple graph, and let e be an edge of G. Then
(6)t(G)=t(G-e)+t(Ge),
where G-e denotes the graph obtained from G by the deletion of e.Combining Lemmas2 and 3, we readily have Lemma 4.Lemma 4.
LetG be a connected graph with e=ij being an edge of G. Then
(7)ΩG(i,j)=t(G)-t(G-e)t(G).For computing resistance distances between adjacent vertices inLn, the number of spanning trees of Ln plays an essential rule.Lemma 5 (see [15–17]).
Consider(8)t(Ln)=28[(3+22)n+1-(3-22)n+1].Now we are arriving at Theorem6.Theorem 6.
Resistance distances between pairs of adjacent vertices of a linear polyacene could be computed as follows.
For1≤k≤n,
(9)ΩLn(ak,bk)=ΩLn(bk,ak+1)=ΩLn(ak′,bk′)=ΩLn(bk′,ak+1′)=([1-28+28(3-22)2k](3+22)n+1-[1+28-28(3+22)2k](3-22)n+1[1-28+28(3-22)2k])×((3+22)n+1-(3-22)n+1)-1,
for 1≤k≤n+1,
(10)ΩLn(ak,ak′)=22([1+(3-22)2k-1](3+22)n+1+[1+(3+22)2k-1](3-22)n+1)×((3+22)n+1-(3-22)n+1)-1.Proof.
We first compute resistance distances between adjacent degree two and degree three vertices. For1≤k≤n, by the structure of Ln, we could see that
(11)ΩLn(ak,bk)=ΩLn(bk,ak+1)=ΩLn(ak′,bk′)=ΩLn(bk′,ak+1′).
By Lemma 4, we have
(12)ΩLn(ak,bk)=t(Ln)-t(Ln-akbk)t(Ln).
Notice that the number of spanning trees of the graph Ln-akbk is equal to the product of the number of spanning trees of Lk-1 and the number of spanning trees of Ln-k (here the number of spanning trees of L0 is regarded as 1, and the formula in Lemma 5 is also applicable to L0); that is,
(13)t(Ln-akbk)=t(Lk-1)t(Ln-k).
Hence,
(14)ΩLn(ak,bk)=t(Ln)-t(Lk-1)t(Ln-k)t(Ln).
Substituting (8) into the above equality, we could obtain (9). It should be mentioned that to obtain (9), one should notice that 3+22 is the reciprocal of 3-22.
Now, we compute resistance distances between{ak,ak′} (1≤k≤n+1). Denote by Sn the graph obtained from Ln by contracting the edge a1b1; that is, Sn=Ln/a1b1. Noticing that the number of spanning trees of Ln-a1b1 is equal to the number of spanning trees of Ln-1, by Lemma 3, simple calculation leads to
(15)t(Sn)=t(Ln)-t(Ln-a1b1)=t(Ln)-t(Ln-1)=24[(2+1)2n+1+(2-1)2n+1].
If we regard the number of spanning trees of S0 as 1, then (15) also holds for n=0. Let Ln/akak′ be the graph obtained from Ln by contracting the edge akak′. Then it is not hard to observe that
(16)t(Lnakak′)=t(Sk-1)t(Sn-k+1).
Hence, by Lemma 2, for 1≤k≤n+1,
(17)ΩLn(ak,ak′)=t(Ln/akak′)t(Ln)=t(Sk-1)t(Sn-k+1)t(Ln).
Substituting (8) and (15) into the above equality, we could obtain (10).


### 2.2. The Global Cyclicity Index of Benzenoid Chains

In [8], Klein and Ivanciuc obtained the following result in Lemma 7.Lemma 7 (see [8]).
All benzenoid chains with the same number of hexagons have the same global cyclicity index.Now we are ready to give the main result of the paper.Theorem 8.
LetHn be a benzenoid chain with n hexagons. Then
(18)C(Hn)=4∑k=1n‍([1-(3-22)2k](3+22)n+1+[1+(3+22)2k](3-22)n+1)×([42-1+(3-22)2k](3+22)n+1-[42+1-(3+22)2k](3-22)n+1)-1+∑k=1n+1‍([2-1-(3-22)2k-1](3+22)n+1-[2+1+(3+22)2k-1](3-22)n+1)×([1-(3-22)2k-1](3+22)n+1+[1+(3+22)2k-1](3-22)n+1)-1.Proof.
By Lemma7, we only need to compute the global cyclicity index of Ln. On one hand, by (9) in Theorem 6, for 1≤k≤n, we have
(19)σLn(ak,bk)-1=σLn(bk,ak+1)-1=σLn(ak′,bk′)-1=σLn(bk′,ak+1′)-1=((3+22)n+1-(3-22)n+1)×([1-28+28(3-22)2k](3+22)n+1-[1+28-28(3+22)2k](3-22)n+1)-1-1=([1-(3-22)2k](3+22)n+1+[1+(3+22)2k](3-22)n+1)×([42-1+(3-22)2k](3+22)n+1-[42+1-(3+22)2k](3-22)n+1)-1.
On the other hand, by (10), for 1≤k≤n+1, we have
(20)σLn(ak,ak′)-1=(2[(3+22)n+1-(3-22)n+1])×([1+(3-22)2k-1](3+22)n+1+[1+(3+22)2k-1](3-22)n+1)-1-1=([2-1-(3-22)2k-1](3+22)n+1-[2+1+(3+22)2k-1](3-22)n+1)×([1-(3-22)2k-1](3+22)n+1+[1+(3+22)2k-1](3-22)n+1)-1.
By the definition of the global cyclicity index, it follows that
(21)C(G)=∑k=1n‍[(bk′,ak+1′)σLn(ak,bk)-1+σLn(bk,ak+1)-1+σLn(ak′,bk′)-1+σLn(bk′,ak+1′)-1]+∑k=1n+1‍[σLn(ak,ak′)-1]=4∑k=1n‍[σLn(ak,bk)-1]+∑k=1n+1‍[σLn(ak,ak′)-1].
Then (18) could be obtained by substituting (19) and (20) into (21).As numerical results, global cyclicity indices of benzenoid chains fromH1 to H50 are listed in Table 1.Table 1
G
Kf(G)
G
Kf(G)
G
Kf(G)
G
Kf(G)
G
Kf(G)
H
1
1.2
H
11
13.927
H
21
26.669
H
31
39.39
H
41
52.122
H
2
2.469
H
12
15.2
H
22
27.932
H
32
40.664
H
42
53.395
H
3
3.7419
H
13
16.474
H
23
29.205
H
33
41.937
H
43
54.668
H
4
5.0151
H
14
17.747
H
24
30.478
H
34
43.21
H
44
55.942
H
5
6.2883
H
15
19.02
H
25
31.752
H
35
44.483
H
45
57.215
H
6
7.5614
H
16
20.293
H
26
33.025
H
36
45.756
H
46
58.488
H
7
8.8346
H
17
21.566
H
27
34.298
H
37
47.029
H
47
59.761
H
8
10.108
H
18
22.839
H
28
35.571
H
38
48.303
H
48
61.034
H
9
11.318
H
19
24.113
H
29
36.844
H
39
49.576
H
49
62.307
H
10
12.654
H
20
25.386
H
30
38.117
H
40
50.849
H
50
63.581


## 2.1. Resistance Distances between Adjacent Vertices in Linear Polyacenes

In this subsection, we will compute resistance distances between pairs of adjacent vertices in linear polyacenes. Denote byLn the linear polyacene with n hexagons. For convenience, we label the vertices of Ln as depicted in Figure 1.A benzenoid chain withn hexagons (a) and the linear polyacene Ln (b).
(a)
(b)To compute resistance distances between pairs of adjacent vertices inLn, we need to employ the classical result of computing resistance distances in terms of spanning trees and spanning bi-trees. A spanning tree (resp., forest) of a connected graph G is a subgraph that contains all the vertices and is a tree (resp., forest). A spanning bi-tree of a connected graph is defined as a spanning forest of the graph with exactly two components. A spanning bi-tree is said to separate vertices i and j if the vertices i and j are in distinct components of the bi-tree. For a connected graph G and for any two vertices i,j∈V(G), we denote by t(G) and t(G;i,j) the number of spanning trees of G and the number of spanning bi-trees of G separating i and j, respectively. Then resistance distances can be computed as given in the following Lemma.Lemma 1 (see [14]).
LetG be a connected graph. Then the resistance distance between any two vertices i and j in G can be computed as
(4)ΩG(i,j)=t(G;i,j)t(G).Now suppose thati and j are adjacent in G, and let e be an edge connecting them. If T is a spanning tree that contains e, then by the deletion of e from T we could obtain a spanning bi-tree F separating i and j. Conversely, if F is a spanning bi-tree separating i and j, then by adding an new edge e connecting i and j to F we could obtain a spanning tree of G. So, the number of spanning trees containing e is equal to the number of spanning bi-trees separating i and j. While, on the other hand, the number of spanning trees of G that contain e is equal to the number of spanning trees of the graph G/e, where G/e denotes the graph obtained from G by contracting e, that is, deleting e and then identifying two end vertices of e. Thus, as a consequence of Lemma 1, we have the following result.Lemma 2.
LetG be a connected graph with e=ij∈E(G). Then
(5)ΩG(i,j)=t(G/e)t(G).In the enumeration of spanning trees of graphs, there is a famous recursion formula, known as the deletion-contraction recurrence. As stated in the following lemma, the recursion formula is applicable tomultiple graphs (i.e., graphs with multiple edges).Lemma 3.
LetG be a multiple graph, and let e be an edge of G. Then
(6)t(G)=t(G-e)+t(Ge),
where G-e denotes the graph obtained from G by the deletion of e.Combining Lemmas2 and 3, we readily have Lemma 4.Lemma 4.
LetG be a connected graph with e=ij being an edge of G. Then
(7)ΩG(i,j)=t(G)-t(G-e)t(G).For computing resistance distances between adjacent vertices inLn, the number of spanning trees of Ln plays an essential rule.Lemma 5 (see [15–17]).
Consider(8)t(Ln)=28[(3+22)n+1-(3-22)n+1].Now we are arriving at Theorem6.Theorem 6.
Resistance distances between pairs of adjacent vertices of a linear polyacene could be computed as follows.
For1≤k≤n,
(9)ΩLn(ak,bk)=ΩLn(bk,ak+1)=ΩLn(ak′,bk′)=ΩLn(bk′,ak+1′)=([1-28+28(3-22)2k](3+22)n+1-[1+28-28(3+22)2k](3-22)n+1[1-28+28(3-22)2k])×((3+22)n+1-(3-22)n+1)-1,
for 1≤k≤n+1,
(10)ΩLn(ak,ak′)=22([1+(3-22)2k-1](3+22)n+1+[1+(3+22)2k-1](3-22)n+1)×((3+22)n+1-(3-22)n+1)-1.Proof.
We first compute resistance distances between adjacent degree two and degree three vertices. For1≤k≤n, by the structure of Ln, we could see that
(11)ΩLn(ak,bk)=ΩLn(bk,ak+1)=ΩLn(ak′,bk′)=ΩLn(bk′,ak+1′).
By Lemma 4, we have
(12)ΩLn(ak,bk)=t(Ln)-t(Ln-akbk)t(Ln).
Notice that the number of spanning trees of the graph Ln-akbk is equal to the product of the number of spanning trees of Lk-1 and the number of spanning trees of Ln-k (here the number of spanning trees of L0 is regarded as 1, and the formula in Lemma 5 is also applicable to L0); that is,
(13)t(Ln-akbk)=t(Lk-1)t(Ln-k).
Hence,
(14)ΩLn(ak,bk)=t(Ln)-t(Lk-1)t(Ln-k)t(Ln).
Substituting (8) into the above equality, we could obtain (9). It should be mentioned that to obtain (9), one should notice that 3+22 is the reciprocal of 3-22.
Now, we compute resistance distances between{ak,ak′} (1≤k≤n+1). Denote by Sn the graph obtained from Ln by contracting the edge a1b1; that is, Sn=Ln/a1b1. Noticing that the number of spanning trees of Ln-a1b1 is equal to the number of spanning trees of Ln-1, by Lemma 3, simple calculation leads to
(15)t(Sn)=t(Ln)-t(Ln-a1b1)=t(Ln)-t(Ln-1)=24[(2+1)2n+1+(2-1)2n+1].
If we regard the number of spanning trees of S0 as 1, then (15) also holds for n=0. Let Ln/akak′ be the graph obtained from Ln by contracting the edge akak′. Then it is not hard to observe that
(16)t(Lnakak′)=t(Sk-1)t(Sn-k+1).
Hence, by Lemma 2, for 1≤k≤n+1,
(17)ΩLn(ak,ak′)=t(Ln/akak′)t(Ln)=t(Sk-1)t(Sn-k+1)t(Ln).
Substituting (8) and (15) into the above equality, we could obtain (10).


## 2.2. The Global Cyclicity Index of Benzenoid Chains

In [8], Klein and Ivanciuc obtained the following result in Lemma 7.Lemma 7 (see [8]).
All benzenoid chains with the same number of hexagons have the same global cyclicity index.Now we are ready to give the main result of the paper.Theorem 8.
LetHn be a benzenoid chain with n hexagons. Then
(18)C(Hn)=4∑k=1n‍([1-(3-22)2k](3+22)n+1+[1+(3+22)2k](3-22)n+1)×([42-1+(3-22)2k](3+22)n+1-[42+1-(3+22)2k](3-22)n+1)-1+∑k=1n+1‍([2-1-(3-22)2k-1](3+22)n+1-[2+1+(3+22)2k-1](3-22)n+1)×([1-(3-22)2k-1](3+22)n+1+[1+(3+22)2k-1](3-22)n+1)-1.Proof.
By Lemma7, we only need to compute the global cyclicity index of Ln. On one hand, by (9) in Theorem 6, for 1≤k≤n, we have
(19)σLn(ak,bk)-1=σLn(bk,ak+1)-1=σLn(ak′,bk′)-1=σLn(bk′,ak+1′)-1=((3+22)n+1-(3-22)n+1)×([1-28+28(3-22)2k](3+22)n+1-[1+28-28(3+22)2k](3-22)n+1)-1-1=([1-(3-22)2k](3+22)n+1+[1+(3+22)2k](3-22)n+1)×([42-1+(3-22)2k](3+22)n+1-[42+1-(3+22)2k](3-22)n+1)-1.
On the other hand, by (10), for 1≤k≤n+1, we have
(20)σLn(ak,ak′)-1=(2[(3+22)n+1-(3-22)n+1])×([1+(3-22)2k-1](3+22)n+1+[1+(3+22)2k-1](3-22)n+1)-1-1=([2-1-(3-22)2k-1](3+22)n+1-[2+1+(3+22)2k-1](3-22)n+1)×([1-(3-22)2k-1](3+22)n+1+[1+(3+22)2k-1](3-22)n+1)-1.
By the definition of the global cyclicity index, it follows that
(21)C(G)=∑k=1n‍[(bk′,ak+1′)σLn(ak,bk)-1+σLn(bk,ak+1)-1+σLn(ak′,bk′)-1+σLn(bk′,ak+1′)-1]+∑k=1n+1‍[σLn(ak,ak′)-1]=4∑k=1n‍[σLn(ak,bk)-1]+∑k=1n+1‍[σLn(ak,ak′)-1].
Then (18) could be obtained by substituting (19) and (20) into (21).As numerical results, global cyclicity indices of benzenoid chains fromH1 to H50 are listed in Table 1.Table 1
G
Kf(G)
G
Kf(G)
G
Kf(G)
G
Kf(G)
G
Kf(G)
H
1
1.2
H
11
13.927
H
21
26.669
H
31
39.39
H
41
52.122
H
2
2.469
H
12
15.2
H
22
27.932
H
32
40.664
H
42
53.395
H
3
3.7419
H
13
16.474
H
23
29.205
H
33
41.937
H
43
54.668
H
4
5.0151
H
14
17.747
H
24
30.478
H
34
43.21
H
44
55.942
H
5
6.2883
H
15
19.02
H
25
31.752
H
35
44.483
H
45
57.215
H
6
7.5614
H
16
20.293
H
26
33.025
H
36
45.756
H
46
58.488
H
7
8.8346
H
17
21.566
H
27
34.298
H
37
47.029
H
47
59.761
H
8
10.108
H
18
22.839
H
28
35.571
H
38
48.303
H
48
61.034
H
9
11.318
H
19
24.113
H
29
36.844
H
39
49.576
H
49
62.307
H
10
12.654
H
20
25.386
H
30
38.117
H
40
50.849
H
50
63.581



---

*Source: 483962-2013-10-21.xml*