# Hosoya Index ofL-Type Polyphenyl Spiders

Authors: Ren Shengzhang; Wu Tingzeng
Journal: Journal of Chemistry
 (2016)

---

## Abstract

The polyphenyl system is composed ofn hexagons obtained from two adjacent hexagons that are sticked by a path with two vertices. The Hosoya index of a graph G is defined as the total number of the independent edge sets of G. In this paper, we give a computing formula of Hosoya index of a type of polyphenyl system. Furthermore, we characterize the extremal Hosoya index of the type of polyphenyl system.


---

## Body

## 1. Introduction

The polyphenyl system is composed ofn hexagons obtained from two adjacent hexagons that are sticked by a path P2. Polyphenyl systems are of great importance for theoretical chemistry because they are natural molecular graph representations of benzenoid hydrocarbons [1]. Polyphenyl systems are graph representations of an important subclass of benzenoid molecules.A topological index is a numerical quantity derived in a unambiguous manner from the structure graph of a molecule. As a graph structural invariant, it does not depend on the label or the pictorial representation of that graph. Various topological indices usually reflect the molecular size and shape. One topological index is Hosoya index, which was first introduced by Hosoya [2]. It plays an important role in the so-called inverse structure-property relationship problems. For details of Hosoya index and its applications, the readers are suggested to refer to [1, 3–5] and references therein. For other topological indices, please see [6–23], among others.In this paper, our aim is to find the computation formula of Hosoya index of a polyphenyl system. We present some definitions and notations as follows.LetG=(V,E) be a graph with vertex set V(G) and edge set E(G). Let e and u be an edge and a vertex of G, respectively. We will denote by G-e or G-u the graph obtained from G by removing e or u, respectively. Denote by Nu the set {v∈V(G):uv∈E(G)}∪{u}. Let H be a subset of V(G). The subgraph of G induced by H is denoted by G[H], and G[V∖H] is denoted by G-H.Two edges ofG are said to be independent if they are not adjacent in G. A k-matching of G is a set of k mutually independent edges. Denote by m(G,k) the number of the k-matchings of G. For convenience, let m(G,0)=1 for any graph G. TheHosoya index of G, denoted by Z(G), is defined as (1)ZG=∑k=0n/2mG,k,where n stands for the order, the number of vertices, of G and n/2 is the integer part of n/2.We denote bydH(G) hexagonal degree of a polyphenyl system graph, which is the number of hexagons sticked by three P2′s. A polyphenyl system graph G is called the polyphenyl spider (see Figure 1) if dH(G)=1 and called polyphenyl chain if dH(G)=0. Let polyphenyl chain s(n) be composed of n hexagons B1,B2,…,Bn obtained from two vertices of adjacent hexagons Bi and Bi+1 that are vertex-sticked by two end vertices of path P2, respectively. If the two vertex sets of Bi(i=2,3,…,n-1) in s(n) divided by two path P2′s both have two vertices, then it is called a linear polyphenyl chain, denoted by l(n). Let g(n),h(n), and q(n) be induced subgraph of l(n) with n hexagons obtained by deleting some vertices (see Figures 2 and 3).Figure 1
L-type polyphenyl spider.Figure 2
Chainsl(n) and g(n).Figure 3
Chainsq(n) and h(n).We denote byΨn the set of polyphenyl spiders with n hexagons. A polyphenyl spider G is called a L-type polyphenyl spider and denote L(i,j,k) where n=i+j+k+1 if three branches of G after deleting the hexagon which sticked by three paths P2 are linear polyphenyl chains.


## 2. Some Lemmas

In this section, we will give some lemmas which will be used later.Lemma 1 (see [1]).
LetG be a graph consisting of two components G1 and G2. Then(2)ZG=ZG1ZG2.Lemma 2 (see [1]).
LetG be a graph and any uv∈E(G). Then(3)ZG=ZG-uv+ZG-u-v.By Lemmas1 and 2, we can obtain the following two results.Lemma 3.
Letl(n) be a linear polyphenyl chain with n hexagons and g(n), h(n), and q(n) be three chains with n-1 hexagons. Then(i)
Z(g(n))=8Z(l(n-1))+4Z(g(n-1)),(ii)
Z(q(n))=8Z(l(n-1))+3Z(g(n-1)),(iii)
Z(h(n))=3Z(l(n-1))+Z(g(n-1)).Lemma 4.
LetL(i,j,k) be a L-type polyphenyl spider with n hexagons. Then (4)ZLi,j,k=ZlkZliZlj+ZlkZgiZqj+ZgkZliZqj+ZgkZgiZhj.Lemma 5 (see [24]).
LetF(n) and L(n) be a Fibonacci and Lucas sequences, respectively. Then(i)
F(n)=αn-βn/5, L(n)=αn+βn, where α=1+5/2 and β=1-5/2,(ii)
F(n)F(m)=1/5(L(n+m)-(-1)nL(m-n)),(iii)
F(m)L(n)=F(n+m)-(-1)mF(n-m)=F(m+n)+(-1)nF(m-n).Lemma 6 (see [25]).
Letq1,q2,…,qt be all different roots of the homogeneous recursive formula Hn=a1Hn-1+a2Hn-1+⋯+akH(n-k). And let ei be the multiplicity of qi(i=1,2,…,t). Then the general solution H(n) of homogeneous recursive formula is H(n)=H1(n)+H2(n)+⋯+Ht(n), where Hi(n)=(c1+c2n+⋯+ceinei-1)qin for i=1,2,…,t.Lemma 7 (see [25]).
LetH(n)=a1H(n-1)+a2H(n-1)+⋯+akH(n-k)+τn be the nonhomogeneous recursive formula, where a1,a2,…,ak and τ are constants. If f(n) is the general solution of homogeneous recursive formula H(n)=a1H(n-1)+a2H(n-1)+⋯+akH(n-k), then the general solution H(n) of the above nonhomogeneous recursive formula can be expressed as H(n)=d1f(n)+d2τn, where d1 and d2 are fixed constants.Lemma 8 (see [26]).
Letl(n) be a linear polyphenyl chain with n hexagons. Then (5)Zln=18818884n-2188.Furthermore, Lemma8 also can be expressed as another form, that is, the following lemma.Lemma 9 (see [26]).
Letl(n) be the linear polyphenyl chain with n hexagons. Then (6)Zln=21922+2062113113λ1n-2+21922-2062113113λ2n-2.


## 3. Main Results

Theorem 10.
Letl(n) be a linear polyphenyl chain with n hexagons and g(n), h(n), and q(n) be three chains with n-1 hexagons. Then(i)
Z(g(n))=175376+16496113/113(λ1-4)λ1n-2+175376-16496113/113(λ2-4)λ2n-2,(ii)
Z(q(n))=8[452226+42542113/113(λ1-4)λ1n-3+452226-42542113/113(λ2-4)λ2n-3],(iii)
Z(h(n))=1334756+125564113/113(λ1-4)λ1n-3+1334756-125564113/113(λ2-4)λ2n-3.Proof.
Combining Lemmas3 and 8 and (i) of Theorem 10, it is easy to prove (ii) and (iii) of Theorem 10. We only prove (i) of Theorem 10 as follows.
By Lemma3, we have (7)Zgn=8Zln-1+4Zgn-1.By Lemma 9, we get that (8)Zgn-4Zgn-1=821922+2062113113λ1n-3+21922-2062113113λ2n-3.By Lemma 6, solving the homogeneous recursive formula Z(g(n))-4Z(g(n-1))=0 of (8), we obtain that Z(g(n))=4n. By Lemma 7, the general solution of the nonhomogeneous recursive formula (8) can be expressed as (9)Zgn=d14n+d2821922+2062113113λ1n-3+21922-2062113113λ2n-3,where d1 and d2 are fixed constants. For the sake of simplicity, we set d3=8d2(21922+2062113/113) and d4=8d2(21922-2062113/113). Then the general solution of the nonhomogeneous recursive formula (9) can be expressed as (10)Zgn=d14n+d3λ1n-3+d4λ2n-3,where d1, d3, d4 are fixed constants. Substituting (10) into the nonhomogeneous recursive formula (8), we get that (11)d3=175376+16496113λ1113λ1-4,d4=175376-16496113λ2113λ2-4,(12)Zgn=d14n+175376+16496113λ1113λ1-4λ1n-3+175376-16496113λ2113λ2-4λ2n-3.
By direct calculation, we getZ(g(4))=82368. By (12), we have d1=0. And the proof of Theorem 10 is complete.Theorem 11.
LetL(i,j,k) be the L-type polyphenyl spider with n hexagons. Then (13)ZLi,j,k=10961+1031113212937331+8143151134×1133λ1k+i+j-7+102439324+37001131132λ1k+j-5λ2i-2+λ1i+j-5λ2k-2+26150912-24555521131132λ1j-3λ2k+i-4+21922+20621131995598080+1865925121131133λ1k+i-4λ2j-3+102439324-37001131132λ1k-2λ2i+j-5+λ1i-2λ2k+j-5+21922+20621132675966-635901131133λ2k+i+j-7.Proof.
For the sake of facilitating the calculation, we set the coefficients of all formulas of Lemma8 and Theorem 10 as follows:(14)a=21922+2062113113,b=21922-2062113113,c=175376+16496113113λ1-4,d=175376-16496113113λ2-4,e=452226+42542113113λ1-4,w=452226-42542113113λ2-4,u=1334756+125564113113λ1-4,v=1334756-125564113113λ2-4.
By Lemma4, we know that (15)ZLi,j,k=ZlkZliZlj+ZlkZgiZqj+ZgkZliZqj+ZgkZgiZhj.By Lemma 9 and Theorem 10, simplifying (15), we have (16)ZLi,j,k=aλ1k-2+bλ2k-2aλ1i-2+bλ2i-2aλ1j-2+bλ2j-2+aλ1k-2+bλ2k-2cλ1i-2+dλ2i-28eλ1j-2+8wλ2j-2+cλ1k-2+dλ2k-2aλ1i-2+bλ2i-28eλ1j-2+8wλ2j-2+cλ1k-2+dλ2k-2cλ1i-2+dλ2i-2uλ1j-2+vλ2j-2=a3λ1+16ace+c2uλ1k+i+j-7+b2aλ1+16bde+d2uλ1j-3λ2k+i-4+a2bλ1+8ade+8bce+cduλ1k+j-5λ2i-2+λ1i+j-5λ2k-2+ab2λ2+8adw+8bcw+cdvλ1k-2λ2i+j-5+λ1i-2λ2k+j-5+a2bλ2+8adw+8bcw+c2vλ1k+i-4λ2j-3+b3λ2+16bdw+d2vλ2k+i+j-7=10961+1031113212937331+8143151134×1133λ1k+i+j-7+102439324+37001131132λ1k+j-5λ2i-2+λ1i+j-5λ2k-2+26150912-24555521131132λ1j-3λ2k+i-4+21922+20621131995598080+1865925121131133λ1k+i-4λ2j-3+102439324-37001131132λ1k-2λ2i+j-5+λ1i-2λ2k+j-5+21922+20621132675966-635901131133λ2k+i+j-7.By Theorem11, we can obtain two corollaries as follows.Corollary 12.
LetL(i,j,k) be a L-type polyphenyl spider with n hexagons. Then (17)ZLi,j,k≥ZLn-13,n-13,n-130mod3,ZLn-23,n-23,n+131mod3,ZLn-33,n3,n32mod3.Particularly, the equality holds if and only if (18)ZLi,j,k≅ZLn-13,n-13,n-130mod3,ZLn-23,n-23,n+131mod3,ZLn-33,n3,n32mod3.Corollary 13.
LetL(i,j,k) be the L-type polyphenyl spider with n hexagons. Then (19)ZLi,j,k≤ZL1,1,n-3,where the equality holds if and only if Z(L(i,j,k))≅Z(L(1,1,n-3)).


## 4. Conclusion

In this paper, applying the relation between inhomogeneous constant coefficient recursion formula and constant coefficient recursion formula, we give a computing formula of Hosoya index of aL-type polyphenyl spider. Furthermore, we determine completely the L-type polyphenyl spider which has the largest and smallest Hosoya index.



---

*Source: 2053293-2016-11-24.xml*