# Sharp Bounds for the Second-Order General Connectivity Index of Hexagonal Chains

Authors: Deqiang Chen
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

GivenH, a hexagonal chain, we determine an expression of its second-order general connectivity index, denoted by  χ2α(H), in terms of inlet features of H. Moreover, by applying the method in integer programming theory, we completely determine the extremal chains with the minimal or maximal χ2α(H) over the set of hexagonal chains.


---

## Body

## 1. Introduction

Ahexagonal system is a finite connected plane graph without cut vertices, in which every interior face is bounded by a regular hexagon of side of length one. A hexagonal system with n hexagons is called an n-hexagonal system for short. Hexagonal systems are of great importance for theoretical chemistry because they are the natural graph representation of benzenoid hydrocarbons. A considerable amount of research in mathematical chemistry has been devoted to hexagonal systems [1–5].The following definitions were introduced in [6, 7]. Suppose H is a hexagonal system. We can associate to each path u1-u2-⋯-uk+1 of length k in H, with the vertex degree sequence (du1,du2,…,duk+1). If one goes along the perimeter of H, then afissure, bay, cove, andfjord are, respectively, paths of degree sequences (2,3,2), (2,3,3,2), (2,3,3,3,2), and (2,3,3,3,3,2) (see Figure 1(i)). The fissures, bays, coves, and fjords are called various types ofinlets. The number of inlets of H is defined as the sum of the numbers of fissures, bays, coves, and fjords.Figure 1
Fissure, bay, cove, fjord, and hexagonal chains.A hexagonal system without internal vertex is called acatacondensed (hexagonal) system. A hexagonal system is calleda hexagonal chain if it has no hexagon adjacent to more than two hexagons. Denote by V3=V3(H) the set of vertices of degree 3 in H. For an n-hexagonal chain H, its induced subgraph H[V3] is an acyclic graph. Moreover, if the subgraph H[V3] is matching with n-1 edges, then H is called alinear (hexagonal) chain and denoted by Ln. If the subgraph H[V3] is a path, then H is called azig-zag chain and denoted by Zn. Some examples of hexagonal chains can be found in Figure 1(ii), where H[V3] are indicated by heavy edges. For a simple graph G and an interger k≥1, the kth-order general connectivity index of G is defined as(1)χkαG=∑u1-u2-⋯-uk+1du1du2⋯duk+1α,where the sum goes over all paths u1-u2-⋯-uk+1 of length k in G (we do not distinguish between the paths u1-u2-⋯-uk+1 and uk+1-⋯-u2-u1), dui(1≤i≤k+1) is the degree of vertex ui, and α is a real number not equal to 0.In general, fork≥2, we call χkα(G) thehigher-order general connectivity index of G.Thekth-order general connectivity index χkα(G) is a natural generalization of some topological indices in mathematical chemistry. It is well known that χ1-1/2(G), called theconnectivity index of G, was introduced by Randić in 1975 in the study of branching properties of alkanes. χk-1/2(G) is called the kth-order connectivity index of G and was considered in 1976 by Randić, Kier, Hall, and coworkers [8] with the intention of extending the applicability of the connectivity index. Moreover, χ1α(G) is thegeneral connectivity index (also called thegeneral Randić index) of G, which was studied in 1998 by Bollobás and Erdös [9].Experimental results show that these indices are closely correlated with many physical, chemical, and biological properties and found to parallel the boiling point, solubility, toxicity, Kovats constants, and a calculated surface. For the results related to the mathematical properties of these indices, please refer to the literature [10].There are many contributions on the mathematical properties of these indices for hexagonal systems. In [11], the authors proved that χ1-1/2(H) is completely determined by the numbers of hexagons and inlets of H. Hexagonal systems with extremal χ1-1/2(H) have also been found [6]. Rada [7] gave an expression of χ2-1/2(H) and found the extremal value over the set of catacondensed systems. For a catacondensed system H, Zheng [12] gave a formula for computing χ1α(H), and the catacondensed systems with the first up to the third extremal value of χ1α(H) were completely characterized. For other results, please refer to [13–17].In this work, we are interested in the second-order general connectivity indices of hexagonal chains. It is shown in Theorem1 that, for a hexagonal chain H, χ2α(H) is completely determined by the numbers of hexagons, bays, coves, and fjords of H. The expression for χ2α(H) is applied in Theorem 4 to obtain the extremal hexagonal chains with the minimal or maximal χ2α(H) among all hexagonal chains with n hexagons.


## 2. A Formula for Computingχ2αH

Theorem 1.
For ann-hexagonal chain H with B bays (n≥2), C coves, and F fjords, its second-order general connectivity index χ2α(H) is equal to(2)χ2αH=4·8α+2n+2+C+2F12α+6n-8-2B-6C-10F18α+2B+5C+8F27α.Proof.
We will prove this theorem by mathematical induction method. IfB=C=F=0, then H is a linear chain with n hexagons. Its second-order general connectivity index χ2α(H) is 4·8α+(2n+2)12α+(6n-8)18α. So (2) is true for B=C=F=0.
Now we apply induction onF. Assume H is a hexagonal chain with B bays, C coves, and F fjords and (2) holds for any hexagonal chain with ≤B bays, ≤C coves, and <F fjords. Suppose v1-u1-u2-u3-u4-v2 is a fjord in H. Then dv1=dv2=2 and du1=du2=du3=du4=3. Let u5 be the vertex so that (u2,u5) is an edge of H and u5≠u1, u5≠u3. Let u6 be the vertex so that (u3,u6) is an edge of H and u6≠u2, u6≠u4. Cut H into three parts H′, H″ and a single hexagon along the edges (u2,u5) and (u3,u6), respectively. See Figure 2.
SupposeH′ has n1 hexagons, B1 bays, C1 coves, and F1 fjords and H″ has n2 hexagons, B2 bays, C2 coves, and F2 fjords. Then n=n1+n2+1, B=B1+B2, C=C1+C2, and F=F1+F2+1. Using the inductive hypothesis, (3)χ2αH′=4·8α+2n1+2+C1+2F112α+6n1-8-2B1-6C1-10F118α+2B1+5C1+8F127αand (4)χ2αH″=4·8α+2n2+2+C2+2F212α+6n2-8-2B2-6C2-10F218α+2B2+5C2+8F227α.
Note that when we cutH into H′, H″ and a single hexagon following the above method, only the paths in H which contain at least one element in {u2,u3,u5,u6} have been changed. Comparing χ2α(H), χ2α(H′), and χ2αH″, we have (5)χ2αH=χ2αH′+χ2αH″-4·8α-4·12α-2·18α+6·12α+6·18α+8·27α=4·8α+2n1+n2+1+2+C1+C2+2F1+F2+112α+6n1+n2+1-8-2B1+B2-6C1+C2-10F1+F2+118α+2B1+B2+5C1+C2+8F1+F2+127α=4·8α+2n+2+C+2F12α+6n-8-2B-6C-10F18α+2B+5C+8F27α.So (2) is true for H with B bays, C coves, and F fjords.
Similarly, we can apply inductions onB and C, respectively. Then the proof for the theorem is completed.Figure 2
The change from H to H′ and H″.


## 3. Extremal Problem

As mentioned in [11], for an n-hexagonal system H with B bays, C coves, and F fjords, the number of bay regions in H is B+2C+3F. Furthermore, if H is an n-hexagonal chain, then each hexagon in H corresponds to at most one bay region and the two hexagons which are the ends of H correspond to no bay region. So the following lemma is obvious.Lemma 2.
SupposeH is an n-hexagonal chain with B bays, C coves, and F fjords. Then B+2C+3F≤n-2.The next lemma plays a significant role in the proof of the main results in this section.Lemma 3.
SupposeH is an n(n≥3,n∈Z)-hexagonal chain with B bays, C coves, and F fjords. Let α∈R and c1=2·27α-2·18α, c2=12α-6·18α+5·27α/2, and c3=2·12α-10·18α+8·27α/3. Then, for the function f(B,C,F)=c1B+2c2C+3c3F, we have (1)
f(B,C,F)≥c1(n-2) for α<0(2)
(6)fB,C,F≤2c2+c3n-4forn-2≡2mod⁡3c3n-3forn-2≡1mod⁡3c3n-2forn-2≡0mod⁡3andα<α1∗, where α1∗(≈-3.969) is the negative root of the equation 12x-6·18x+5·27x=0Proof.
Firstly, ifα<0, then it is easy to get c1<0 and c1<c2<c3. By Lemma 2, B+2C+3F≤n-2. Then f(B,C,F)=c1B+2c2C+3c3F≥c1(B+2C+3F)≥c1(n-2). The equalities hold if and only if C=F=0 and B=n-2.
Secondly, ifα<α1∗, then c1<0<c2<c3. We next apply the methods in the theory of linear programming and integer programming. (For the notations and terminology not introduced here, please refer to [18] for more details.) Consider a linear integer programming problem (IP) and its corresponding linear programming relaxation problem (LR). (7)IPmaxfB,C,F=c1B+2c2C+3c3Fs.t.B+2C+3F≤n-2B,C,F≥0B,C,Fare integersLRmaxfB,C,F=c1B+2c2C+3c3Fs.t.B+2C+3F≤n-2B,C,F≥0By the simplex method, we know the optimal solution for (LR) is (n-2)c3 with (B,C,F)=(0,0,n-2/3).
By the branch-and-bound method, ifn-2≡0(mod⁡3), then the optimal solution (n-2)c3 for (LR) is exactly the optimal solution for (IP). Then for (IP), max⁡f(B,C,F)=c3(n-2).
Ifn-2≡2(mod⁡3), then by applying the branch-and-bound method, we obtain that the optimal solution for (IP) is max⁡f(B,C,F)=2c2+c3(n-4) with (B,C,F)=(0,1,n-4/3). The flow diagram is shown in Figure 3.
Ifn-2≡1(mod⁡3), then, by the branch-and-bound method, the optimal solution for (IP) is max⁡f(B,C,F)=c3(n-3) with (B,C,F)=(0,0,n-3/3). The flow diagram is shown in Figure 4. Then we prove(8)fB,C,F≤2c2+c3n-4forn-2≡2mod⁡3c3n-3forn-2≡1mod⁡3c3n-2forn-2≡0mod⁡3forα<α1∗.Figure 3
The diagram for the casen-2≡2(mod⁡3).Figure 4
The diagram for the casen-2≡1(mod⁡3).Theorem 4.
Forn≥3, the extremal n-hexagonal chains with minimal second-order general connectivity index χ2α are shown in Table 1.Table 1 α α < 0 α > 0  hexagonal chains with minimalχ2α the zig-zag chainZn the linear hexagonal chainLnProof.
LetLn and Zn be the linear hexagonal chain and the zig-zag chain with n hexagons, respectively. Obviously, Ln has no bay, cove, or fjord and Zn only has n-2 bays, 0 coves, and 0 fjords. By Theorem 1,(9)χ2αLn=4·8α+2n+212α+6n-818α,χ2αZn=4·8α+2n+212α+4n-418α+2n-427α.Suppose H is an n-hexagonal chain with B bays, C coves, and F fjords. Then, by Lemma 2 and Theorem 1, we have 0≤B≤n-2, 0≤2C≤n-2, 0≤3F≤n-2, and (10)χ2αH=4·8α+2n+2+C+2F12α+6n-8-2B-6C-10F18α+2B+5C+8F27α.
Comparingχ2α(H) and χ2α(Ln), we have (11)χ2αH-χ2αLn=2·27α-2·18αB+12α-6·18α+5·27αC+2·12α-10·18α+8·27αF.
Ifα>0, then 2·27α-2·18α>0, 12α-6·18α+5·27α>0, 2·12α-10·18α+8·27α>0. Thus we have χ2α(H)≥χ2α(Ln). The equality holds if and only if B=C=F=0(H=Ln). Then we prove that Ln is the unique extremal hexagonal chain with minimal χ2α when α>0.
Comparingχ2α(H) and χ2α(Zn), we have (12)χ2αH-χ2αZn=2n-418α-27α+2·27α-2·18αB+12α-6·18α+5·27αC+2·12α-10·18α+8·27αF.
By Lemma3, if α<0, χ2αH-χ2αZn≥(2n-4)(18α-27α)+(n-2)(2·27α-2·18α)=0. The equality holds if and only if B=n-2 and C=F=0(H=Zn). Then we prove that Zn is the unique extremal hexagonal chain with minimal χ2α when α<0.LetH(B,C,F) be the set of n-hexagonal chains so that H∈H(B,C,F) if and only if H is a hexagonal chain with F fjords, C coves, and B bays. Obviously, H(0,0,0)={Ln} and H(n-2,0,0)={Zn}.Theorem 5.
Forn≥3, the extremal n-hexagonal chains with maximal second-order general connectivity index χ2α are shown in Table 2, where α1∗(≈-3.969) and α2∗(≈-3.419) are the negative roots of the equations 12x-6·18x+5·27x=0 and 2·12x-10·18x+8·27x=0, respectively.Table 2 α hexagonal chains with maximalχ2α   (-∞,α1∗) H ∈ H 0,1 , n - 2 3 i f   n - 2 ≡ 2 ( mod ⁡ 3 ) H 0,0 , n - 2 3 o t h e r s   α=α1∗ H ∈ H 0,1 , n - 2 3 ∪ H 0,0 , n - 2 3   (α1∗,α2∗) H ∈ H 0,0 , n - 2 3  α=α2∗ n-hexagonal chains without coves nor bays  (α2∗,0) L n   (0,+∞) H ∈ H 0,0 , n - 2 3 i f   n - 2 ≡ 0 ( mod ⁡ 3 ) H 0,1 , n - 2 3 i f   n - 2 ≡ 2 ( mod ⁡ 3 ) H 1,0 , n - 2 3 i f   n - 2 ≡ 1 ( mod ⁡ 3 )Proof.
We here only prove the results for the case thatα∈(-∞,α1∗). Other cases are completely similar. Suppose H is an n-hexagonal chain with B bays, C coves, and F fjords. By Theorem 1, we have χ2α(H)=4·8α+(2n+2+C+2F)12α+(6n-8-2B-6C-10F)18α+(2B+5C+8F)27α. As defined in Lemma 3, c1, c2, and c3 denote 2·27α-2·18α, 12α-6·18α+5·27α/2, and 2·12α-10·18α+8·27α/3, respectively.(1)
Ifn-2≡2(mod⁡3) and H∗∈H0,1,n-2/3, then H∗ has 0 bays, 1 cove, and n-4/3 fjords. By Theorem 1, χ2α(H∗)=4·8α+(8n+1/3)12α+(8n-2/3)18α+(8n-17/3)27α. Then, by Lemma 3, (13)χ2αH-χ2αH∗=c1B+2c2C+3c3F+12α5-2n3+18α10n-223+27α17-8n3≤2c2+c3n-4+12α5-2n3+18α10n-223+27α17-8n3=0.Thus we prove thatχ2α(H)≤χ2α(H∗).(2)
Ifn-2≡1(mod⁡3) and H∗∈H(0,0,⌊n-2/3⌋), then H∗ has 0 bays, 0 coves, and n-3/3 fjords. By Theorem 1, χ2α(H∗)=4·8α+(8n/3)12α+(8n+6/3)18α+(8n-24/3)27α. Then, by Lemma 3, (14)χ2αH-χ2αH∗=c1B+2c2C+3c3F+12α6-2n3+18α10n-303+27α24-8n3≤c3n-3+12α6-2n3+18α10n-303+27α24-8n3=0.Thus we prove thatχ2α(H)≤χ2α(H∗).(3)
Ifn-2≡0(mod⁡3) and H∗∈H(0,0,⌊n-2/3⌋), then H∗ has 0 bays, 0 coves, and n-2/3 fjords. By Theorem 1, χ2α(H∗)=4·8α+(8n+2/3)12α+(8n-4/3)18α+(8n-16/3)27α. Then, by Lemma 3, (15)χ2αH-χ2αH∗=c1B+2c2C+3c3F+12α4-2n3+18α10n-203+27α16-8n3≤c3n-2+12α4-2n3+18α10n-203+27α16-8n3=0.Thus we prove thatχ2α(H)≤χ2α(H∗).
By the above analysis, we have the following result. Forα∈(-∞,α1∗), if n-2≡2(mod⁡3), then the hexagonal chains in H(0,1,⌊n-2/3⌋) have maximal χ2α; if n-2≡0,1(mod⁡3), then the hexagonal chains in H(0,0,⌊n-2/3⌋) have maximal χ2α.
The discussion for other cases is similar and we omit it here.Example 6.
Table3 shows the second-order general connectivity indices of L22, Z22, and some hexagonal chains in Figure 5. The extremal values are indicated by heavy words.Table 3 L 22 Z 22 H 1 H 2 H 3 H 4 F , C , B 0,0 , 0 0,0 , 20 6,1 , 0 6,0 , 0 6,0 , 1 1,2 , 7  χ   2 α = 4 · 8 α + 46 · 1 2 α + 124 · 1 8 α 4 · 8 α + 46 · 1 2 α + 84 · 1 8 α + 40 · 2 7 α 4 · 8 α + 59 · 1 2 α + 58 · 1 8 α + 53 · 2 7 α 4 · 8 α + 58 · 1 2 α + 64 · 1 8 α + 48 · 2 7 α 4 · 8 α + 58 · 1 2 α + 62 · 1 8 α + 50 · 2 7 α 4 · 8 α + 50 · 1 2 α + 88 · 1 8 α + 32 · 2 7 α  χ   2 5 ≈ 2.5 × 108 7.4 × 1 0 8 8.9 × 108 8.2 × 1 0 8 8.5 × 1 0 8 6.4 × 1 0 8  χ   2 - 1 / 2 ≈ 43.92 42.19 42.31 42.48 42.39 42.75  χ   2 - 3.5 ≈ 0.01545 0.01423 0.01548 0.01550 0.01544 0.01498  χ   2 - 5 ≈ 3.72 × 1 0 - 4 3.54 × 10-4 3.93 × 10-4 3.92 × 1 0 - 4 3.91 × 1 0 - 4 3.71 × 1 0 - 4Figure 5
Some hexagonal chains.



---

*Source: 7506541-2018-09-06.xml*