# Merrifield-Simmons Index in Random Phenylene Chains and Random Hexagon Chains

Authors: Ailian Chen
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

The author obtains explicit expressions for the expected value of the Merrifield-Simmons index of a random phenylene chain and a random hexagon chain, respectively. The author also computes the corresponding entropy constants and obtains the maximum and minimum values in both random systems, respectively.


---

## Body

## 1. Introduction

LetG=(V,E) be a simple undirected graph on n vertices. Two vertices of G are said to be independent if they are not adjacent in G. A k-independent set of G is a set of k mutually independent vertices. Denote by i(G,k) the number of the k-independent sets of G. By definition, the empty vertex set is an independent set. Then i(G,0)=1 for any graph G. The Merrifield-Simmons index of G, denoted by i(G), is defined as i(G)=∑k=0n‍i(G,k). So i(G) is equal to the total number of the independent sets of G. The Merrifield-Simmons index was introduced in 1982 by Prodinger and Tichy [1], where it was called the Fibonacci number of a graph. The Merrifield-Simmons index is one of the most popular topological indices in chemistry intensively studied, as seen in the monograph [2]. Recently, there have been many papers studying the Merrifield-Simmons index for a graph. For more details see [3–8], among others.Phenylenes are a class of conjugated hydrocarbons composed of six- and four-membered rings, where the six-membered rings (hexagons) are adjacent only to four-membered rings, and every four-membered ring is adjacent to a pair of nonadjacent hexagons. If each six-membered ring of a phenylene is adjacent only to two four-membered rings, we say that is a phenylene chain. Due to their aromatic and antiaromatic rings, phenylenes exhibit unique physicochemical properties. In Figure1, some examples of phenylene chains are presented. The unique phenylene chains for n=1 and n=2 are shown in Figure 1. More generally, a phenylene chain with n+1 hexagons (see Figure 2) can be regarded as a phenylene chain PHn, with n hexagons to which a new terminal hexagon has been adjoined by a four-membered ring. But, for n≥3, the terminal hexagon can be attached in three ways, which results in the local arrangements we describe as PHn+11, PHn+12, and PHn+13 (see Figure 3). Naturally, we define a random phenylene chain PH(n,p) with n hexagons as a phenylene chain obtained by stepwise addition of terminal hexagons. At each step k (=3,4,…,n) a random selection is made from one of the three possible constructions: (1) PHk-1→PHk1, with probability p, (2) PHk-1→PHk2, with probability p, or (3) PHk-1→PHk3, with probability q=1-2p.Figure 1
Phenylene chains.Figure 2
P
H
n.Figure 3
The three types of local arrangements in phenylene chains.We assume that the probabilityp is a constant, invariant to the step parameter k. That is, the process described is a zeroth-order Markov process.By eliminating, “squeezing out,” the squares from a phenylene, a catacondensed hexagonal system (which may be jammed) is obtained, called the hexagonal squeeze of the respective phenylene (see Figure4). Clearly, there is a one-to-one correspondence between a phenylene (PH) and its hexagonal squeeze (HS). Both possess the same number of hexagons. The respective hexagonal squeeze of a random phenylene chain PHn,p is a random hexagonal chain, and we denote it by HSn,p.Figure 4
Phenylenes and the corresponding hexagonal squeezes.The Wiener index and the number of perfect matchings of a random hexagonal chainHSn,p have been studied by Gutman et al. [8–10]. Analogous results for a random phenylene chain PHn,p have been obtained by Chen and Zhang in [11]. In this paper we obtain explicit expressions for the expected value of the Merrifield-Simmons index of a random phenylene chain PHn,p and a random hexagonal chain HSn,p, respectively. We also compute the corresponding entropy constants and obtain the maximum and minimum values in both random systems, respectively. For some recent results on these hexagonal structures, see [12, 13].


## 2. Merrifield-Simmons Index of a Random Phenylene Chain

Firstly, let us recall some results in [14], useful to this paper.Lemma 1 (see [14]).
Consideri(G1∪G2)=i(G1)i(G2).Lemma 2 (see [14]).
Letu be a vertex of G and let Nu be the subset of  V(G) consisting of the vertex u and its neighbors. Then (1)i(G)=i(G-u)+i(G-Nu).As described above, the phenylene chainPHn can be obtained by adjoining to PHn-1 a hexagon by a 4-membered ring. For this construction, the following relations are easily obtained by Lemmas 1 and 2.Lemma 3.
LetPHn be denoted as a phenylene chain as in Figure 2; then for n≥2 one has (2)iPHn=8iPHn-1+5[i(PHn-1-an-1)+i(PHn-1-bn-1)],iPHn-a=5i(PHn-1)+5i(PHn-1-an-1)+3i(PHn-1-bn-1),ifa=tn,6i(PHn-1)+3i(PHn-1-an-1)+4i(PHn-1-bn-1),ifa=un,6i(PHn-1)+4i(PHn-1-an-1)+3i(PHn-1-bn-1),ifa=vn,5i(PHn-1)+3i(PHn-1-an-1)+5i(PHn-1-bn-1),ifa=wn.Proof.
Consider(3)iPHn=iPHn-sn+iPHn-1-an-1∪P3=iPHn-1∪P4+iPHn-1-bn-1∪P3+i((PHn-1-an-1)∪P3)=iP4iPHn-1+i(P3)i(PHn-1-bn-1)+i(PHn-1-an-1)=8iPHn-1+5[i(PHn-1-an-1)+i(PHn-1-bn-1)],iPHn-tn=i(PHn-tn-sn)+i((PHn-1-an-1)∪P3)=i(PHn-1∪P3)+i((PHn-1-bn-1)∪P2)+i((PHn-1-an-1)∪P3)=i(P3)i(PHn-1)+i(P2)i(PHn-1-bn-1)+i(P3)i(PHn-1-an-1)=5i(PHn-1)+5i(PHn-1-an-1)+3i(PHn-1-bn-1),iPHn-un=i((PHn-un-sn))+i((PHn-1-an-1)∪P2)=i(PHn-1∪P1∪P2)+i((PHn-1-bn-1)∪2P1)+i((PHn-1-an-1)∪P2)=i(P1)i(P2)i(PHn-1)+i2(P1)i(PHn-1-bn-1)+i(P2)i(PHn-1-an-1)=6i(PHn-1)+3i(PHn-an-1)+4i(PHn-1-bn-1).By the symmetry, (4)iPHn-vn=6iPHn-1+4iPHn-1-an-1+3i(PHn-bn-1),iPHn-wn=5iPHn-1+3iPHn-1-an-1+5i(PHn-1-bn-1).
For a random phenylene chainPHn,p, the Merrifield-Simmons indices i(PHn,p), i(PHn,p-an), and i(PHn,p-bn) are random variables and we denote their expected values by In=E[i(PHn,p)], Un=E[i(PHn,p-an)], and Vn=E[i(PHn,p-bn)], respectively.
By the definition ofPHn,p, we immediately have that, for n≥2,(5)In=8In-1+5[Un-1+Vn-1],Un=pE5iPHn-1,p+5iPHn-1,p-an-1+3i(PHn-1,p-bn-1)+pE6iPHn-1,p+4iPHn-1,p-an-1+3i(PHn-1,p-bn-1)+(1-2p)E6iPHn-1,p+3iPHn-1,p-an-1+4i(PHn-1,p-bn-1)=(6-p)EiPHn-1,p+(3+3p)Ei(PHn-1,p-an-1)+(4-2p)Ei(PHn-1,p-bn-1)=(6-p)In-1+(3+3p)Un-1+(4-2p)Vn-1.
By the symmetry,(6)Vn=(6-p)In-1+(4-2p)Un-1+(3+3p)Vn-1.
To solve the recursion equation, we use the method of the generating functions. Set(7)I(t)=∑n≥1‍Intn,U(t)=∑n≥1‍Untn,V(t)=∑n≥1‍Vntn.Then we have that (8)I(t)-18t=8tI(t)+5t[U(t)+V(t)],Ut-13t=6-ptIt+4-2ptVt+(3+3p)tU(t),Vt-13t=6-ptIt+3+3ptVt+(4-2p)tU(t).Recall that I1=18, I2=274, and U1=V1=13.
Solving the equations, we have that(9)It=2t9+2t-9pt1-15t-pt-4t2+18pt2=At1-15+p+241-42p+p2/2t+Bt1-15+p-241-42p+p2/2t,where (10)A=9+139-9p241-42p+p2241-42p+p2,B=9-139-9p241-42p+p2241-42p+p2.So we have the following result.Theorem 4.
If0≤p≤1/2, then for n≥2 one has that (11)EiPHn,p=A15+p+241-42p+p22n-1+B15+p-241-42p+p22n-1,where (12)A=9+(139-9p)241-42p+p2241-42p+p2,B=9-(139-9p)241-42p+p2241-42p+p2.
Specifically, one has that(13)EiPHn,1/2=9+26988188131+8814n-1+9-26988188131-8814n-1,EiPHn,1/3=9+20451151123+5113n-1+9-20451151123-5113n-1,EiPHn,0=9+13924124115+2412n-1+9-13924124115-2412n-1.The following corollary is easily obtained from Theorem4 which gives the limits of the entropy constant log⁡E[i(PHn,p)]/|V(PHn,p)| as n→+∞, where V(PHn,p) is the vertex set of PHn,p.Corollary 5.
If0≤p≤1/2, then for n≥2, one has (14)limn→+∞log⁡EiPHn,pVPHn,p=limn→+∞log⁡E[i(PHn,p)]6n=15+p+241-42p+p212.
It is easy to check thatf(p)=(15+p+241-42p+p2)/12 is a monotonic decreasing function on p, so the limit of log⁡E[i(PHn,p)]/6n has the maximum value (15+241)/12≈2.5437 at p=0 and the minimum value (31+881)/24≈2.5284 at p=1/2. That is say, for different p (0≤p≤1/2), the limit of log⁡E[i(PHn,p)]/6n has little difference.


## 3. Merrifield-Simmons Index of a Random Hexagon Chain

Similar to the phenylene chainPHn, the hexagon chain HSn can be obtained by adjoining to HSn-1 a hexagon. For this construction the following relations are easily obtained by Lemmas 1 and 2.Lemma 6.
LetHSn be denoted as a hexagon squeeze of a phenylene chain PHn as in Figure 2; then for n≥2 one has (15)iHSn=3iHSn-1+2iHSn-1-an-1+iHSn-1-bn-1+i(HSn-1-an-1-bn-1),i(HSn-a)=3i(HSn-1)+2i(HSn-1-bn-1),ifa=tn,2i(HSn-1)+2i(HSn-1-an-1)+i(HSn-1-bn-1)+i(HSn-1-an-1-bn-1),ifa=un,2i(HSn-1)+i(HSn-1-an-1)+2i(HSn-1-bn-1)+i(HSn-1-an-1-bn-1),ifa=vn,3i(HSn-1)+2i(HSn-1-an-1),ifa=wn,i(HSn-a-b)=2i(HSn-1)+i(HSn-1-bn-1),ifa=tn,b=un,i(HSn-1)+i(HSn-1-an-1)+i(HSn-1-bn-1)+i(HSn-1-an-1-bn-1),ifa=un,b=vn,2i(HSn-1)+i(HSn-1-an-1),ifa=vn,b=wn.Proof.
Consider(16)iHSn=i(HSn-tn)+i(HSn-tn-an-1-un)=iHSn-1∪P2+iHSn-1-bn-1∪P1+i((HSn-1-an-1)∪P1)+i(HSn-1-an-1-bn-1)=iP2iHSn-1+i(P1)[i(HSn-1-bn-1)+i(HSn-1-an-1)]+i(HSn-1-an-1-bn-1)=3iHSn-1+2[i(HSn-1-an-1)+i(HSn-1-bn-1)]+i(HSn-1-an-1-bn-1),i(HSn-tn)=i(HSn-1∪P2)+i((HSn-1-bn-1)∪P1)=i(P2)i(HSn-1)+i(P1)i(HSn-1-bn-1)=3i(HSn-1)+2i(HSn-1-bn-1),iHSn-un=iHSn-un-tn+i(HSn-1-un-tn-an-1)=iHSn-1∪P1+iHSn-1-bn-1+i((HSn-1-an-1)∪P1)+i(HSn-1-an-1-bn-1)=iP1iHSn-1+iHSn-1-bn-1+i(P1)i(HSn-1-an-1)+i(HSn-1-an-1-bn-1)=2iHSn-1+2iHSn-an-1+i(HSn-1-bn-1)+i(HSn-1-an-1-bn-1),iHSn-tn-un=i(HSn-1∪P1)+i(HSn-1-bn-1)=i(P1)i(HSn-1)+i(HSn-1-bn-1)=2i(HSn-1)+i(HSn-1-bn-1),iHSn-un-vn=iHSn-un-vn-tn+i(HSn-un-vn-tn-an-1)=iHSn-1+iHSn-1-bn-1+iHSn-1-an-1+i(HSn-1-an-1-bn-1).By the symmetry,(17)iHSn-vn=2iHSn-1+iHSn-an-1+2i(HSn-1-bn-1)+i(HSn-1-an-1-bn-1),i(HSn-wn)=3i(HSn-1)+2i(HSn-1-an-1),i(HSn-vn-wn)=2i(HSn-1)+i(HSn-1-an-1).
For a random hexagon chainHSn,p, the Merrifield-Simmons indices i(HSn,p), i(HSn,p-an), i(HSn,p-bn), and i(HSn,p-an-bn) are also random variables, and in not confusion circumstances we also denote their expected values by In=E[i(HSn,p)], Un=E[i(HSn,p-an)], Vn=E[i(HSn,p-bn)], and Wn=E[i(HSn,p-an-bn)], respectively. Then we immediately have that, for n≥2, (18)In=3In-1+2[Un-1+Vn-1]+Wn-1,Un=pEiHSn,p-tn+pEiHSn,p-vn+(1-2p)E[i(HSn,p-un)]=pE3iHSn-1,p+2iHSn-1,p-bn-1+pE2i(HSn-1,p)+i(HSn-1,p-an-1)h+pE+2i(HSn-1,p-bn-1)h+pE+i(HSn-1,p-an-1-bn-1)+(1-2p)·E2i(HSn-1,p)+2iHSn-1,p-an-1+iHSn-1,p-bn-1+i(HSn-1,p-an-1-bn-1)=2+pEiHSn-1,p+(2-3p)E[i(HSn-1,p-an-1)]+1+2pEiHSn-1,p-bn-1+(1-p)E[i(HSn-1,p-an-1-bn-1)]=2+pIn-1+2-3pUn-1+1+2pVn-1+1-pWn-1,Wn=pEiHSn,p-tn-un+pEiHSn,p-vn-wn+(1-2p)E[i(HSn,p-un-vn)]=pE2iHSn-1,p+iHSn-1,p-bn-1+p[2i(HSn-1,p)+i(HSn-1,p-an-1)]+(1-2p)Ei(HSn-1,p)+i(HSn-1,p-bn-1)mmmmmmmm+i(HSn-1,p-an-1)mmmmmmmm+i(HSn-1,p-an-1-bn-1)=1+2pEiHSn-1,p+(1-p)E[i(HSn-1,p-an-1)]+1-pEiHSn-1,p-bn-1+(1-2p)E[i(HSn-1,p-an-1-bn-1)]=(1+2p)In-1+(1-p)Un-1+(1-p)Vn-1+(1-2p)Wn-1.
By the symmetry,(19)Vn=2+pIn-1+1+2pUn-1+(2-3p)Vn-1+(1-p)Wn-1.
Just as above, we set(20)I(t)=∑n≥1‍Intn,U(t)=∑n≥1‍Untn,V(t)=∑n≥1‍Vntn,W(t)=∑n≥1‍Wntn.Then we have that (21)I(t)-18t=3tI(t)+2t[U(t)+V(t)]+tW(t),Ut-13t=2+ptIt+2-3ptUt+1+2ptVt+1-ptWt,Vt-13t=2+ptIt+1+2ptUt+2-3ptVt+1-ptWt,Wt-8t=1+2ptIt+1-ptUt+1-ptVt+1-2ptWt.Recall that I1=18, U1=V1=13, and W1=8.
Solving the equations, we have that(22)It=6t3-2t+9pt1-7t+6pt+4t2-36pt2=At1-7-3p+33+30p+9p2/2t+Bt1-7-3p-33+30p+9p2/2t,where (23)A=9+(59-9p)33+30p+9p233+30p+9p2,B=9-(59-9p)33+30p+9p233+30p+9p2.So we have the following result.Theorem 7.
If0≤p≤1/2, then for n≥2 one has that (24)EiHSn,p=A7-3p+33+30p+9p22n-1+B7-3p-33+30p+9p22n-1,where(25)A=9+(59-9p)33+30p+9p233+30p+9p2,B=9-(59-9p)33+30p+9p233+30p+9p2.
Specifically, we have that(26)EiHSn,1/2=9+10920120111+2014n-1+9-10920120111-2014n-1,EiHSn,1/3=9+2811113+11n-1+9-2811113-11n-1,EiHSn,0=9+5933337+332n-1+9-5933337-332n-1.The following corollary is easily obtained from Theorem7 which gives the limit of log⁡E[i(HSn,p)]/|V(HSn,p)| as n→+∞, where V(HSn,p) is the vertex set of HSn,p.Corollary 8.
If0≤p≤1/2, then for n≥2, one has (27)limn→+∞log⁡EiHSn,pVHSn,p=limn→+∞log⁡EiHSn,p4n+2=7-3p+33+30p+9p28.
It is easy to check thatg(p)=(7-3p+33+30p+9p2)/8 is a monotonic decreasing function on p, so the limit of log⁡E[i(HSn,p)]/|V(HSn,p)| has the maximum value (7+33)/2≈1.062 at p=0, and the minimum value (11+201)/4≈1.049 at p=1/2. That is say, for different p(0≤p≤1/2), the limit of log⁡E[i(HSn,p)]/|V(HSn,p)| has little difference.



---

*Source: 568926-2015-03-23.xml*