# Perfect Matchings in Random Octagonal Chain Graphs

Authors: Shouliu Wei; Niandong Chen; Xiaoling Ke; Guoliang Hao; Jianwu Huang
Journal: Journal of Mathematics
 (2021)

---

## Abstract

A perfect matching of a (molecule) graphG is a set of independent edges covering all vertices in G. In this paper, we establish a simple formula for the expected value of the number of perfect matchings in random octagonal chain graphs and present the asymptotic behavior of the expectation.


---

## Body

## 1. Introduction

A general problem of interest in chemistry, physics, and mathematics is the enumeration of perfect matchings, on lattices and (molecule) graphs. LetG be a graph. A perfect matching of G is a set of independent edges covering all vertices in G, which is called Kekulé structure in organic chemistry and closed-packed dimer in statistical physics. In organic chemistry, there are strong connections between the number of the Kekulé structures and chemical properties for many molecules such as benzenoid hydrocarbons [1–3]. The number of Kekulé structures is an important topological index which had been applied for estimation of the resonant energy and total π-electron energy [2, 4] and Clar aromatic sextet [5]. In crystal physics, the perfect matching problem is closely related to the dimer problem [6–8]. Denote the number of perfect matchings of a graph G by ΦG.An octagonal system (graph) [9] is a finite 2-connected geometric graph in which every interior face is bounded by a regular octagon or quadrangle of side length 1 (see Figure 1). Octagonal graphs have attracted many mathematicians’ considerable attentions because of many interest combinatorial subjects. Brunvoll et al. [9] determined the number of isomers of tree-like octagonal graphs by the generating functions. Su and Ding [10] showed that there is a side whose relative length is at most 1 in every convex octagon, and this bound is asymptotically tight. In 2001, Destainville et al. [11] considered some combinatorial properties of fixed-boundary octagonal random tilings. Yang and Zhao [12] presented a relation between the number of perfect matching in octagonal chain graphs and Hosoya index of the caterpillar trees in 2013. Wei et al. [13]discussed the Wiener indices in a type of random octagonal chains in 2018.Figure 1
Three octagonal graphs: (a)G1, (b) G2, and (c) G3.
(a)(b)(c)An octagonal graph, called an octagonal chain graph, proved that no octagon is adjacent to more than two other octagons. Both the octagonal graphsG2 and G3 are octagonal chain graphs, as shown in Figure 1. Let G be an octagonal chain graph with n≥3 octagons labeled by o1,o2,…,on, where oi and oi+1 are adjacent for each i (i=1,2,…,n−1). Both the first octagon o1 and the last octagon on are called terminal octagon. And, the remaining octagons o2,o3,…,on−1 are called internal octagon. Each internal octagon is one of type A, type L, or type S according to whether it separates its two adjacent octagons by a distance of 3, 1, or 2, as shown in Figure 2. A random octagonal chain graph of length n is an octagonal chain graph with n octagons in which each internal octagon is one of type A with probability p, type L with probability q, or type L with probability 1−p−q, denoted by Gn,p,q. Gutman [14, 15] studied the perfect matchings about random benzenoid chain graphs in 1990s. Chen and Zhang [16] obtained a simple exact formula for the expected value of the number of perfect matchings in a random phenylene chain. Simple exact formulae are presented for the expected value of the number of perfect matchings in random polyomino chain graphs by Wei et al. [17] in 2016. Recently, Wei and Shiu [18] obtained the expected value of the number of perfect matchings in random polyazulenoid chains.Figure 2
Three types of internal octagons. (a)A. (b) L. (c) S.
(a)(b)(c)In this paper, we establish an exact formula for the expected value of the number of perfect matchings in a random octagonal chain graph.


## 2. The Number of Perfect Matchings in Random Octagonal Chain Graphs

In this section, we consider the expected value of the number of perfect matchings in a random octagonal chain graph. We will keep the notation defined in Section1. Recall that there is a recursive formula for the perfect matchings in G [4], i.e.,(1)ΦG=ΦG−u−v+ΦG−uv,where uv denotes an edge of G incident with the vertices u and v. All notations which are not defined in this paper can be found in [19].Lemma 1.
LetGi be an octagonal chain graph with i octagons. Then,(2)ΦG1=2,ΦG2=3,and for i≥3,(3)ΦGi=ΦGi−1+ΦGi−2,if thei−1−th octagon is of typeAorL,2ΦGi−1−ΦGi−2,if thei−1−th octagon is of typeS.Proof.
Without loss of generality, lete=uv be an edge in the octagonal chain graph Gi, as shown in Figures 3 and 4.Case 1. Suppose the i−1th octagon is of type A or L. It is easy to see from Figure 3 that(4)ΦGi−u−v=ΦGi−1,ΦGi−e=ΦGi−2.Thus, we get the result by (1), i.e.,(5)ΦGi=ΦGi−1+ΦGi−2.Case 2. Suppose the i−1th octagon is of type S. It is easy to see from Figure 4 that(6)ΦGi−u−v=ΦGi−1,ΦGi−e=ΦGi−1−ΦGi−2.
Thus, we get the result by (1), i.e.,(7)ΦGi=2ΦGi−1−ΦGi−2.
This completes the proof.
Note that the probabilitiesp and q are unknown constants. Here, ΦGn,p,q is a random variable. Denote the expected value of ΦGn,p,q by EΦGn,p,q.Figure 3
Illustrations of case 1 in Lemma1: (a) type A; (b) type L.
(a)(b)Figure 4
Illustrations of case 2 in Lemma1. (a) Gi. (b) Gi−u−v. (c) Gi − e.
(a)(b)(c)Lemma 2.
LetGi,p,q be a random octagonal chain graph with i octagons. Then,(8)EΦGi,p,q=2−p−qEΦGi−1,p,q+2p+q−1EΦGi−2,p,q,where i≥3.Proof.
Since thei−1th octagon of Gn,p,q is one of type A with probability p, type L with probability q, and type S with probability 1−p−q, we have(9)EΦGi,p,q=2−p−qΦGi−1,p,q+2p+q−1ΦGi−2,p,q,by Lemma 1. Recall that EEΦGi,p,q=EΦGi,p,q. Since EΦGi,p,q is a sum of random variables, we have(10)EΦGi,p,q=2−p−qEΦGi−1,p,q+2p+q−1EΦGi−2,p,q.
Thus, the proof is completed.Theorem 1.
LetGi,p,q be a random octagonal chain graph with i octagons.(1)
Ifp+q>0, then, for each i≥2,(11)EΦGi+1,p,q=2r−3r−ssi−2s−3r−sri,where(12)r=2−p−q+p+q2+4p+q2,s=2−p−q−p+q2+4p+q2.(2)
Ifp+q=0, then(13)EΦGi+1,0,0=2+i.Proof.
Letei=EΦGi+1,p,q and i≥0. Since ΦG1=2 and ΦG2=3, we have the initial conditions e0=2, e1=3. By Lemma 2, we have(14)ei=2−p−qei−1+2p+q−1ei−2,for i≥2. Note that the characteristic equation of (14) is(15)λ2−2−p−qλ−2p+q−1=0,and its characteristic roots are(16)λ1=2−p−q+p+q2+4p+q2≜r,λ2=2−p−q−p+q2+4p+q2≜s.Case 1. If p+q>0, then r≠s. In this case,(17)ei=k1ri+k2si.Substituting the boundary conditionse0=2 and e1=3, we obtain(18)k1=−2s−3r−s,k2=2r−3r−s.Therefore,(19)ei=EΦGi+1,p,q=−2s−3r−sri+2r−3r−ssi,which proves the first statement of the theorem.Case 2. If p+q=0, then r=s=1. Thus, ei=k1+k2i, and we have(20)k1=2,k2=1,which means that ei=EΦGi+1,p,q=i+2.
LetPn, On, and Mn be the parachain, orthochain, and metachain with n octagons, as shown in Figure 5. By assuming p=1, q=1, and p=q=0, respectively, we can obtain the number of Kekulé structures of Pn, On, and Mn from Theorem 1.Figure 5
The parachainPn, orthochain On, and metachain Mn with n octagons. (a) Pn. (b) On. (c) Mn.
(a)(b)(c)Corollary 1.
LetPn, On, and Mn be the parachain, orthochain, and metachain with n octagons. Then,(1)
ΦPn=5+35/101+5/2n+5−35/101−5/2n(2)
ΦOn=5+35/101+5/2n+5−35/101−5/2n(3)
ΦMn=n+1
It is suggested that the functionEΦGn,p,q has interest in mathematics and chemistry in [14], especially concerning its asymptotic behavior with respect to n. From the explicit expression for EΦGn,p,q in Theorem 1, we have the following result.Corollary 2.
LetGn,p,q be a random cyclooctane chain graph with n octagons. If p+q>0, then(21)limn⟶∞EΦGn,p,qEΦGn−1,p,q=r,where(22)r=2−p−q+p+q2+4p+q2.Proof.
Ifp+q>0, then(23)r=2−p−q+p+q2+4p+q2,s=2−p−q−p+q2+4p+q2,by Theorem 1. And, by the explicit expression of EΦGn,p,q, we have(24)EΦGn,p,qEΦGn−1,p,q=k1rn−1+k2sn−1k1rn−2+k2sn−2=r+sk2/k1s/rn−21+k2/k1s/rn−2.
Sincer>s, we obtain(25)limn⟶∞EΦGn,p,qEΦGn−1,p,q=r.
Thus, the proof is completed.



---

*Source: 2324632-2021-06-23.xml*