# On the Hosoya Indices of Bicyclic Graphs with Small Diameter

Authors: Tingzeng Wu; Yong Yu
Journal: Journal of Chemistry
 (2021)

---

## Abstract

LetG be a graph. The Hosoya index of G, denoted by zG, is defined as the total number of its matchings. The computation of zG is NP-Complete. Wagner and Gutman pointed out that it is difficult to obtain results of the maximum Hosoya index among tree-like graphs with given diameter. In this paper, we focus on the problem, and a sharp bound of Hosoya indices of all bicyclic graphs with diameter of 3 is determined.


---

## Body

## 1. Introduction

Hosoya index is an important topological index introduced by Hosoya [1]. It was found that Hosoya index is related to a variety of physicochemical properties of alkanes (= saturated hydrocarbons). In particular, the boiling points of alkanes are well correlated with Hosoya index. Another series of researches revealed the applicability of Hosoya index in the theory of conjugated π-electron systems [2, 3]. Jerrum [4] showed that the computing complexity of Hosoya index is NP-Complete. The Hosoya index got much attention by many researchers in the past decades. They have been interested in identifying the extremal value of Hosoya index for various classes of graphs, such as trees [5–7], unicyclic graphs [8–12], bicyclic graphs [13], and n,m-graphs [14, 15]. Wagner and Gutman [16] gave an exhaustive survey for Hosoya index, and they pointed out some open problems (also see [17]) as follows:•
It seems difficult to obtain results of the maximum Hosoya index among trees with a given number of leaves or given diameter. However, partial results are available, so the problem might not be totally intractable, and results in this direction would definitely be interesting.•
If the aforementioned questions can be answered for trees, then it is also natural to consider the analogous questions for tree-like graphs.According to the open problems, Liu et al. [17] discussed the problem in which unicyclic graph with diameter of 3 or 4 has the maximum Hosoya index. In this paper, we focus on similar problems to the above. That is, which bicyclic graph with diameter of 3 has the maximum Hosoya index? We give an answer of the problem as follows.Theorem 1.
G∈ℬn3 and n≥10; each of the following holds:(1)iIf10≤n≤15.ThenzG≤32n2−8n+16,wherenis even, and the equality holdsiffG≅G14n−42,n−62;32n2−8n+20,wherenis odd, and the equality holdsiffG≅G14n−52,n−52,iiIfn≥16.ThenzG≤2n3−6n2+63n−5427,wheren≡0mod3,and the equality holdsiffG≅G10n−33,n3,n−33;2n3−6n2+60n−5627,wheren≡1mod3,and the equality holds iffG≅G10n−13,n−13,n−43≅G10n−43,n−13,n−13;2n3−6n2+63n−6427,wheren≡2mod3,and the equality holdsiffG≅G10n−23,n−23,n−23.The rest of this paper is organized as follows. In Section2, we shall present some definitions and lemmas. In Section 3, we will prove Theorem 1. Furthermore, some upper bounds for Hosoya index of some special classes of bicyclic graphs with diameter of 3 are also determined.


## 2. Preliminaries

In this paper, we only consider finite and simple graphs. LetG=VG,EG be a graph with n vertices and m edges. The neighborhood of vertex v∈VG in a graph G, denoted by NGv, is the set of vertices adjacent to v. The degree of v, denoted by dv, is the number of neighbors of v in G. The distance of two vertices u,v∈VG is the length of a shortest path from u to v, denoted by dGu,v. We will use G−v to represent the graph after G deleting the vertex v. The diameter of G is max dGu,v|u,v∈vG.Letℬn3 be the set of all bicyclic graphs with n vertices and diameter of 3. It is easy to verify that the structure of graph G∈ℬn3 must be isomorphic to Gi, where i=1,2,…,14. The resulting graph Gi can be seen in Figure 1.Figure 1
All bicyclic graphsGi,i=1,2,…,14, with diameter of 3.LetmG,k be the number of k-matchings of G. It is convenient to denote mG,0=1 and mG,k=0 for k>⌊n/2⌋. The Hosoya index of G, denoted by zG, is defined as the sum of all the numbers of its matchings; namely,(2)zG=∑k=0n/2mG,k.Lemma 1 (see [16]).
LetG be a graph and let v be a vertex of graph G. Then(i)
zG=zG−v+∑u∈NGvzG−u,v(ii)
zG=∏i=1tzGi, where Gi is a component of GLetG be a graph obtained by joining the centers of two stars K1,p−1 and K1,q−1, denoted by Sp,q. By Lemma 1, we obtain the following result.Lemma 2.
(i)
zK1,p=1+p(ii)
zSp,q=pq+1


## 3. The Proof of Theorem 1

In order to prove Theorem1, we first give some lemmas.Lemma 3.
LetG∈G1a,b,c be a graph with n vertices. Then(3)zG≤227n3−3n2+27n−27,wheren≡0mod3,n≥9and the equality holds iffG≅G1n−33,n−33,n3≅G1n−33,n3,n−33≅G1n−63,n3,n3;227n3−3n2+30n−28,wheren≡1mod3,n≥10and the equality holdsiffG≅G1n−43,n−13,n−13;227n3−3n2+27n−23,wheren≡2mod3,n≥11and the equality holdsiffG≅G1n−53,n−23,n+13≅G1n−53,n+13,n−23.Proof.
Consider that vertexv′ of degree 1 is adjacent to v1 in G1a,b,c. By Lemmas 1 and 2, we have zG1a,b,c=2abc+2bc+2a+2b+2c+2. In the following, we use the method of Lagrange multipliers to find the sharp bound of Hosoya index of G∈G1a,b,c. First, we make auxiliary function as follows: La,b,c=λa+b+c+2−n+2abc+2a+2b+2c+2bc+2, where a+b+c+2=n, a,b,c≥1, and at most one of them is 1. Taking the partial derivatives of a,b,c, and λ in La,b,c,λ, we can obtain the following equations:(4)La=λ+2bc+2=0,Lb=λ+2ac+2+2c=0,Lc=λ+2ab+2+2b=0,Lλ=a+b+c+2−n=0,a≥1,b≥1andc≥1.
Solving the equations as above, we obtain thata=n−4/3, b=n−1/3, and c=n−1/3. Because n−4/3,n−1/3,n−1/3 is a unique stable point, n−4/3,n−1/3,n−1/3 must be a unique extreme point. Since a, b, and c are integers, we consider three cases.Case 1: assume thatn≡0mod3. We know that a=n−3/3, b=n−3/3, and c=n/3; a=n−3/3, b=n/3, and c=n−3/3; or a=n−6/3, b=n/3, and c=n/3. Thus, zG1n−3/3,n/3,n−3/3=zG1n−3/3,n−3/3,n/3=zG1n−6/3,n/3,n/3=2/27n3−3n2+27n−27. It is easy to verify that zG1a,b,c<2/27n3−3n2+27n−27 when a≠n−6/3, b≠n/3, and c≠n/3; a≠n−3/3, b≠n/3, and c≠n−3/3; or a≠n−3/3, b≠n−3/3, and c≠n/3 . This implies that zG≤2/27n3−3n2+27n−27 and the equality holds iff G≅G1n−3/3,n−3/3,n/3≅G1n−3/3,n/3,n−3/3≅G1n−6/3,n/3,n/3.Case 2: suppose thatn≡1mod3. We have a=n−4/3, b=n−1/3, and c=n−1/3. So zG1n−4/3,n−1/3,n−1/3=2/27n3−3n2+30n−28. To simplify the calculation, we know that zG1a,b,c<2/27n3−3n2+30n−28 when a≠n−4/3, b≠n−1/3, and c≠n−1/3. This means that zG≤2/27n3−3n2+30n−28 and the equality holds iff G≅G1n−4/3,n−1/3,n−1/3.Case 3: assume thatn≡2mod3. Then a=n−5/3, b=n−2/3, and c=n+1/3; or a=n−5/3, b=n+1/3, and c=n−2/3. Thus, zG1n−5/3,n−2/3,n+1/3=zG1n−5/3,n+1/3,n−2/3=2/27n3−3n2+27n−23. It is easy to check that zG1a,b,c<2/27n3−3n2+27n−23 when a≠n−5/3, b≠n−2/3, and c≠n+1/3; or a≠n−5/3, b≠n+1/3, and c≠n−2/3. This indicates that zG≤2/27n3−3n2+27n−23 and the equality holds if and only if G≅G1n−5/3,n−2/3,n+1/3≅G1n−5/3,n+1/3,n−2/3.Lemma 4.
LetG∈G2a,b be a graph with n vertices. Then(5)zG≤n2−4n+8,wheren≥8is even, and the equality holds iffG≅G2n−62,n−22;n2−4n+7,wheren≥9is odd, and the equality holds iffG≅G2n−72,n−12orG≅G2n−52,n−32.Proof.
Similar to the proof of Lemma3, by Lemmas 1 and 2, we have zG2a,b=4ab+8b+4. By the method of Lagrange multipliers, we make an auxiliary function La,b=λa+b+4−n+4ab+8b+4, where a+b+4=n, a≥1, and b≥2. Taking the partial derivatives of a, b, and λ in La,b,λ, we get the following equations:(6)La=λ+4b=0,Lb=λ+4a+8=0,Lλ=a+b+4−n=0,a≥1andb≥2.
Solving the equations as above, we obtain thata=n−6/2 and b=n−2/2. Because n−6/2,n−2/2 is a unique stable point, n−6/2,n−2/2 must be the unique extreme point. Since a and b are integers, in the following we consider two cases:Case 1: suppose thatn is even. Then a=n−6/2 and b=n−2/2. Thus, zG2n−6/2,n−2/2=4ab+8b+4=n2−4n+8. To simplify calculation, we know that zG2a,b<n2−4n+8 when a≠n−6/2 and b≠n−2/2. This implies that zG≤n2−4n+8 and the equality holds iff G≅G2n−6/2,n−2/2.Case 2: assume thatn is odd. We obtain a=n−7/2 and b=n−1/2, or a=n−5/2 and b=n−3/2. So, zG2n−7/2,n−1/2=zG2n−5/2,n−3/2=n2−4n+7. It is easy to check that zG2a,b<n2−4n+7 when a≠n−7/2 and b≠n−1/2, or a≠n−5/2 and b≠n−3/2. This means that zG≤n2−4n+7 and the equality holds iff G≅G2n−7/2,n−1/2≅G2n−5/2,n−3/2.Lemma 5.
LetG∈G3a,b be a graph with n vertices. Then(7)zG≤n2−4n+8,wheren≥8is even, and the equality holds iffG≅G3n−42,n−42≅G3n−22,n−62;n2−4n+9,wheren≥7is odd, and the equality holds iffG≅G3n−32,n−52.Proof.
Similar to the proof of Lemma3, by Lemmas 1 and 2, we get that zG3a,b=4ab+6a+2b+8. According to the method of Lagrange multipliers, we make an auxiliary function La,b=λa+b+4−n+4ab+6a+2b+8, where a+b+4=n, a≥1, and b≥1. Taking the partial derivatives of a,b, and λ in La,b,λ, we obtain the following equations:(8)La=λ+4b+6=0,Lb=λ+4a+2=0,Lλ=a+b+4−n=0,a≥1andb≥1.
Solving the equations as above, we obtain thata=n−3/2 and b=n−5/2. Because n−3/2,n−5/2 is a unique stable point, n−3/2,n−5/2 must be the unique extreme point. Since a and b are integers, we only consider two cases.Case 1: assume thatn is even. We obtain a=n−4/2 and b=n−4/2, or a=n−2/2 and b=n−6/2. Thus, zG3n−4/2,n−4/2=zG3n−2/2,n−6/2=n2−4n+8. It is easy to check that zG3a,b<n2−4n+8 when a≠n−4/2 and b≠n−4/2, or a≠n−2/2 and b≠n−6/2. This implies that zG≤n2−4n+8 and the equality holds if and only if G≅G3n−4/2,n−4/2≅G3n−2/2,n−6/2.Case 2: consider thatn is odd. We have a=n−3/2 and b=n−5/2. So, zG3n−3/2,n−5/2=n2−4n+9. It is easy to verify that zG3a,b<n2−4n+9 when a≠n−3/2 and b≠n−5/2. This means that zG≤n2−4n+9 and the equality holds if and only if G≅G3n−3/2,n−5/2.Lemma 6.
LetG∈G4a,b be a graph with n vertices. Then(9)zG≤32n2−8n+16,wheren≥8is even,and the equality holds iffG≅G4n−62,n−42;32n2−8n+292,wheren≥7is odd, and the equality holdsiffG≅G4n−52,n−52≅G4n−72,n−32.Proof.
Similar to the proof of Lemma3, by Lemmas 1 and 2, we get zG4a,b=6ab+4a+10b+12. According to the method of Lagrange multipliers, we make an auxiliary function La,b=λa+b+5−n+6ab+4a+10b+12, where a+b+5=n, a≥1 , and b≥1. Taking the partial derivatives of a,b, and λ in La,b,λ, we can obtain the following equations:(10)La=λ+6b+4=0,Lb=λ+6a+10=0,Lλ=a+b+5−n=0,a≥1andb≥1.
Solving the equations as above, we obtain thata=n−6/2 and b=n−4/2. Because n−6/2,n−4/2 is a unique stable point, n−6/2,n−4/2 must be the unique extreme point. Since a and b are integers, we only consider two cases:Case 1: consider thatn is even. We have a=n−6/2 and b=n−4/2. Thus zG4n−6/2,n−4/2=3/2n2−8n+16. To simplify calculation, we get zG4a,b<3/2n2−8n+16 when a≠n−6/2 and b≠n−4/2. This implies that zG≤3/2n2−8n+16 and the equality holds iff G≅G4n−6/2,n−4/2.Case 2: assume thatn is odd. Then a=n−5/2 and b=n−5/2, or a=n−7/2 and b=n−3/2. So zG4n−5/2,n−5/2=zG4n−7/2,n−3/2=3/2n2−8n+29/2. It is easy to check that zG4a,b<3/2n2−8n+29/2 when a≠n−5/2 and b≠n−5/2, or a≠n−7/2 and b≠n−3/2. This implies that zG≤3/2n2−8n+29/2 and the equality holds if and only if G≅G4n−5/2,n−5/2≅G4n−7/2,n−3/2.Lemma 7.
LetG∈G5a,b be a graph with n vertices. Then(11)zG≤n2−4n+8,wheren≥6is even, and the equality holds iffG≅G5n−42,n−42;n2−4n+7,wheren≥7is odd, and the equality holdsiffG≅G5n−32,n−52≅G5n−52,n−32.Proof.
Similar to the proof of Lemma3, by Lemmas 1 and 2, we get zG5a,b=4ab+4a+4b+8. By the method of Lagrange multipliers, we make an auxiliary function La,b=λa+b+4−n+4ab+4a+4b+8, where a+b+4=n, a≥1, and b≥1. Taking the partial derivatives of a,b, and λ in La,b,λ, we can obtain the following equations:(12)La=λ+4b+4=0,Lb=λ+4a+4=0,Lλ=a+b+4−n=0,a≥1andb≥1.
Solving the equations as above, we obtain thata=n−4/2 and b=n−4/2. Because n−4/2,n−4/2 is a unique stable point, n−4/2,n−4/2 must be the unique extreme point. Since a and b are integers, in the following we only consider two cases.Case 1: consider thatn is even. We have a=n−4/2 and b=n−4/2. Thus zG5n−4/2,n−4/2=n2−4n+8. To simplify calculation, we get zG5a,b<n2−4n+8 when a≠n−4/2 and b≠n−4/2. This implies that zG≤n2−4n+8 and the equality holds iff G≅G5n−4/2,n−4/2.Case 2: assume thatn is odd. Then a=n−3/2 and b=n−5/2, or a=n−5/2 and b=n−3/2. So zG5n−3/2,n−5/2=zG5n−5/2,n−3/2=n2−4n+7. It is easy to check that zG5a,b<n2−4n+7 when a≠n−3/2 and b≠n−5/2, or a≠n−5/2 and b≠n−3/2. This implies that zG≤n2−4n+7 and the equality holds if and only if G≅G5n−3/2,n−5/2≅G5n−5/2,n−3/2.Lemma 8.
LetG∈G6a,b,c be a graph with n vertices. Then(13)zG≤n3+3n2+18n+2727,wheren≡0mod3,n≥9and the equality holdsif and only ifG≅G6n−33,n3,n3≅G6n3,n−33,n3;n3+3n2+18n+3227,wheren≡1mod3,n≥7and the equality holdsif and only ifG≅G6n−13,n−13,n−13;n3+3n2+21n+1927,wheren≡2mod3,n≥8and the equality holdsif and only ifG≅G6n−23,n−23,n+13.Proof.
Similar to the proof of Lemma3, by Lemmas 1 and 2, direct computing yields zG6a,b,c=abc+bc+ac+a+b+c+2. By the method of Lagrange multipliers, we make auxiliary function La,b,c=λa+b+c+1−n+abc+bc+ac+a+b+c+2, where a+b+c+1=n, a,b,c≥1, and at most one of them is 1. Taking the partial derivatives of a, b, c, and λ in La,b,c,λ, we can obtain the following equations:(14)La=λ+bc+c+1=0,Lb=λ+ac+c+1=0,Lc=λ+ab+b+a+1=0,Lλ=a+b+c+1−n=0,a≥1,b≥1andc≥1.
Solving the equations as above, we getc=a+1−1/a+1. Since c=a+1−1/a+1 is an integer, we know that c=⌈a+1−1/a+1⌉ or c=⌊a+1−1/a+1⌋. By c=⌈a+1−1/a+1⌉ and a+b+c+1=n, we can obtain that a=n−2/3, b=n−2/3, and c=n+1/3. Similarly, by c=⌊a+1−1/a+1⌋ and a+b+c+1=n, we also can obtain that a=n−1/3, b=n−1/3, and c=n−1/3. Thus, we discuss two cases as follows:Case 1:a=n−2/3, b=n−2/3, and c=n+1/3.Becausea=n−2/3, b=n−2/3, and c=n+1/3 is a unique root of (14), a=n−2/3, b=n−2/3, and c=n+1/3 must be the unique extreme point. Since a, b, and c are integers, we consider three subcases:Subcase 1: assume thatn≡0mod3. Then a=n−3/3, b=n/3, and c=n/3, or a=n/3, b=n−3/3, and c=n/3. Thus zG6n−3/3,n/3,n/3=zG6n/3,n−3/3,n/3=n3+3n2+18n+27/27. It is easy to verify that zG6a,b,c<n3+3n2+18n+27/27 when a≠n−3/3, b≠n−3/3, and c≠n+3/3, or a≠n−3/3, b≠n−3/3, and c≠n+3/3. This implies that zG≤n3+3n2+18n+27/27 and the equality holds if and only if G≅G6n−3/3,n/3,n/3≅G6n/3,n−3/3,n/3.Subcase 2: suppose thatn≡1mod3. Then a=n−1/3, b=n−1/3, and c=n−1/3. Thus zG6n−1/3,n−1/3,n−1/3=n3+3n2+18n+32/27. It is easy to check that zG6a,b,c<n3+3n2+18n+32/27 when a≠n−1/3, b≠n−1/3, and c≠n−1/3. This implies that zG≤n3+3n2+18n+32/27 and the equality holds iff G≅G6n−1/3,n−1/3,n−1/3.Subcase 3: consider thatn≡2mod3. Then a=n−2/3, b=n−2/3, and c=n+1/3. Thus zG6n−2/3,n−2/3,n+1/3=n3+3n2+21n+19/27. To simplify calculation, we know that zG6a,b,c<n3+3n2+21n+19/27 when a≠n−2/3, b≠n−2/3, and c≠n+1/3. This implies that zG≤n3+3n2+21n+19/27 and the equality holds iff G≅G6n−2/3,n−2/3,n+1/3.Case 2:a=n−1/3, b=n−1/3, and c=n−1/3.Similar to the proof of Case 1, becausea=n−1/3, b=n−1/3, and c=n−1/3 is a unique root of (14), a=n−1/3, b=n−1/3, and c=n−1/3 must be the unique extreme point. Since a, b, and c are integers, we also consider the three following subcases:Subcase 1: setn≡0mod3. Then a=n−3/3, b=n/3, and c=n/3, or a=n/3, b=n−3/3, and c=n/3. Thus zG6n−3/3,n/3,n/3=zG6n/3,n−3/3,n/3=n3+3n2+18n+27/27. It is easy to verify that zG6a,b,c<n3+3n2+18n+27/27 when a≠n−3/3, b≠n−3/3, and c≠n+3/3, or a≠n−3/3, b≠n−3/3, and c≠n+3/3. This implies that zG≤n3+3n2+18n+27/27 and the equality holds if and only if G≅G6n−3/3,n/3,n/3≅G6n/3,n−3/3,n/3.Subcase 2: suppose thatn≡1mod3. Then a=n−1/3, b=n−1/3, and c=n−1/3. Thus zG6n−1/3,n−1/3,n−1/3=n3+3n2+18n+32/27. It is easy to check that zG6a,b,c<n3+3n2+18n+32/27 when a≠n−1/3, b≠n−1/3, and c≠n−1/3. This implies that zG≤n3+3n2+18n+32/27 and the equality holds iff G≅G6n−1/3,n−1/3,n−1/3.Subcase 3: consider thatn≡2mod3. Then a=n−2/3, b=n−2/3, and c=n+1/3. Thus zG6n−2/3,n−2/3,n+1/3=n3+3n2+21n+19/27. To simplify calculation, we know that zG6a,b,c<n3+3n2+21n+19/27 when a≠n−2/3, b≠n−2/3, and c≠n+1/3. This implies that zG≤n3+3n2+21n+19/27 and the equality holds iff G≅G6n−2/3,n−2/3,n+1/3.Lemma 9.
LetG∈G7a,b be a graph with n vertices. Then(15)zG≤3n2−8n+164,wheren≥6is even, and the equality holds iffG≅G7n−22,n−42;3n2−8n+174,wheren≥7is odd, and the equality holds iffG≅G7n−12,n−52.Proof.
Similar to the proof of Lemma3, by Lemmas 1 and 2, direct computing yields zG7a,b=3ab+5a+3. By the method of Lagrange multipliers, we make auxiliary function La,b=λa+b+3−n+3ab+5a+3, where a+b+3−n, a≥2, and b≥1. Taking the partial derivatives of a, b, and λ in La,b,λ, we can obtain the following equations:(16)La=λ+3b+5=0,Lb=λ+3a=0,Lλ=a+b+3−n=0,a≥2andb≥1.
Solving the equations as above, we geta=b+5/3. Since a=b+5/3 is an integer, we know that a=⌊b+5/3⌋ or a=⌈b+5/3⌉. By a=⌊b+5/3⌋ and a+b+3=n, we can obtain that a=n−2/2 and b=n−4/2. Similarly, by a=⌈b+5/3⌉ and a+b+3=n, we also can obtain that a=n−1/2 and b=n−5/2. So, we discuss two cases as follows:Case 1:a=n−2/2 and b=n−4/2.Becausea=n−2/2 and b=n−4/2 is a unique root of (16), a=n−2/2 and b=n−4/2 must be the unique extreme point. Since a and b are integers, we consider two subcases:Subcase 1: assume thatn is even. Then a=n−2/2 and b=n−4/2; thus zG7n−2/2,n−4/2=3n2−8n+16/4. It is easy to verify that zG7a,b<3n2−8n+16/4 when a≠n−2/2 and b≠n−4/2. This implies that zG≤3n2−8n+16/4 and the equality holds if and only if G≅G7n−2/2,n−4/2.Subcase 2: suppose thatn is odd. We know that a=n−1/2 and b=n−5/2. Thus zG7n−1/2,n−5/2=3n2−8n+17/4. It is easy to verify that zG7a,b<3n2−8n+17/4 when a≠n−1/2 and b≠n−5/2. This implies that zG≤3n2−8n+17/4 and the equality holds iff G≅G7n−1/2,n−5/2.Case 2:a=n−1/2 and b=n−5/2.Similar to the proof of Case 1, becausea=n−1/2 and b=n−5/2 is a unique root of (2), a=n−1/2 and b=n−5/2 must be the unique extreme point. Since a and b are integers, we also consider two subcases.Subcase 1: consider thatn is even. Then we get a=n−2/2 and b=n−4/2; thus zG7n−2/2,n−4/2=3n2−8n+16/4. It is easy to verify that zG7a,b<3n2−8n+16/4 when a≠n−2/2 and b≠n−4/2. This implies that zG≤3n2−8n+16/4 and the equality holds if and only if G≅G7n−2/2,n−4/2.Subcase 2: assume thatn is odd. We know that a=n−1/2 and b=n−5/2. Thus zG7n−1/2,n−5/2=3n2−8n+17/4. It is easy to verify that zG7a,b<3n2−8n+17/4 when a≠n−1/2 and b≠n−5/2. This implies that zG≤3n2−8n+17/4 and the equality holds iff G≅G7n−1/2,n−5/2.Lemma 10.
LetG∈G8a,b be a graph with n vertices. Then(17)zG≤3n2−8n+164,wheren≥8is even, and the equality holds iffG≅G8n−22,n−42;3n2−8n+294,wheren≥7is odd, and the equality holds iffG≅G8n−32,n−32.Proof.
Similar to the proof of Lemma3, by Lemmas 1 and 2, we get zG8a,b=3ab+3a+2b+5. By the method of Lagrange multipliers, we make an auxiliary function La,b=λa+b+3−n+3ab+3a+2b+5, where a+b+3=n, a,b≥1, and at most one of them is 1. Taking the partial derivatives of a,b, and λ in La,b,λ, we can obtain the following equations:(18)La=λ+3b+3=0,Lb=λ+3a+2=0,Lλ=a+b+3−n=0,a≥1andb≥1.
Solving the equations as above, we geta=b+1/3. Since a=b+1/3 is an integer, we know that a=⌊b+1/3⌋ or a=⌈b+1/3⌉. By a=⌊b+1/3⌋ and a+b+3=n, we can obtain that a=n−3/2 and b=n−3/2. Similarly, by a=⌈b+1/3⌉ and a+b+3=n, we also can obtain that a=n−2/2 and b=n−4/2. So, we discuss two cases as follows:Case 1:a=n−3/2 and b=n−3/2.Becausea=n−3/2 and b=n−3/2 is a unique root of (18), a=n−3/2 and b=n−3/2 must be the unique extreme point. Since a and b are integers, we consider two subcases.Subcase 1: consider thatn is even. We have a=n−2/2 and b=n−4/2. Thus zG8n−2/2,n−4/2=3n2−8n+16/4. To simplify calculation, we get zG8a,b<3n2−8n+16/4 when a≠n−2/2 and b≠n−4/2. This implies that zG≤3n2−8n+16/4 and the equality holds iff G≅G8n−2/2,n−4/2.Subcase 2: assume thatn is odd. Then a=n−3/2 and b=n−3/2. So zG8n−3/2,n−3/2=3n2−8n+29/4. It is easy to check that zG8a,b<3n2−8n+29/4 when a≠n−3/2 and b≠n−3/2. This implies that zG≤3n2−8n+29/4 and the equality holds if and only if G≅G8n−3/2,n−3/2.Case 2:a=n−2/2 and b=n−4/2.Similar to the proof of Case 1, becausea=n−2/2 and b=n−4/2 is a unique root of (18), a=n−2/2 and b=n−4/2 must be the unique extreme point. Since a and b are integers, we consider two subcases.Subcase 1: consider thatn is even. We have a=n−2/2 and b=n−4/2. Thus zG8n−2/2,n−4/2=3n2−8n+16/4. To simplify calculation, we get zG8a,b<3n2−8n+16/4 when a≠n−2/2 and b≠n−4/2. This implies that zG≤3n2−8n+16/4 and the equality holds iff G≅G8n−2/2,n−4/2.Subcase 2: assume thatn is odd. Then a=n−3/2 and b=n−3/2. So zG8n−3/2,n−3/2=3n2−8n+29/4. It is easy to check that zG8a,b<3n2−8n+29/4 when a≠n−3/2 and b≠n−3/2. This implies that zG≤3n2−8n+29/4 and the equality holds if and only if G≅G8n−3/2,n−3/2.Lemma 11.
LetG∈G9a,b be a graph with n vertices. Then(19)zG≤n2−4n+8,wheren≥8is even, and the equality holds iffG≅G2n−62,n−22;n2−4n+7,wheren≥9is odd, and the equality holds iffG≅G2n−72,n−12OrG≅G2n−52,n−32.Proof.
Similar to the proof of Lemma3, by Lemmas 1 and 2, we get zG9a,b=4ab+2a+2b+5. By the method of Lagrange multipliers, we make an auxiliary function La,b=λa+b+3−n+4ab+2a+2b+5, where a+b+3=n, a,b≥1, and at most one of them is 1. Taking the partial derivatives of a,b, and λ in La,b,λ, we can obtain the following equations:(20)La=λ+4b+2=0,Lb=λ+4a+2=0,Lλ=a+b+3−n=0,a≥1andb≥1.
Solving the equations as above, we obtain thata=n−3/2 and b=n−3/2. Because n−3/2,n−3/2 is a unique stable point, n−3/2,n−3/2 must be the unique extreme point. Since a and b are integers, we consider the two following cases.Case 1: consider thatn is even. We have a=n−2/2 and b=n−4/2, or a=n−4/2 and b=n−2/2. Thus zG9n−2/2,n−4/2=zG9n−4/2,n−2/2=n2−4n+7. To simplify calculation, we get zG9a,b<n2−4n+7 when a≠n−2/2 and b≠n−4/2, or a≠n−4/2 and b≠n−2/2. This implies that zG≤n2−4n+7 and the equality holds iff G≅G9n−2/2,n−4/2≅G9n−4/2,n−2/2.Case 2: assume thatn is odd. We know that a=n−3/2 and b=n−3/2. Thus zG9n−3/2,n−3/2=n2−4n+8. It is easy to check that zG9a,b<n2−4n+8 when a≠n−3/2 and b≠n−3/2. This implies that zG≤n2−4n+8 and the equality holds if and only if G≅G9n−3/2,n−3/2.Lemma 12.
LetG∈G10a,b,c be a graph with n vertices. Then(21)zG≤2n3−6n2+63n−5427,wheren≡0mod3,n≥9and the equality holdsif and only ifG≅G10n−33,n3,n−33;2n3−6n2+60n−5627,wheren≡1mod3,n≥10and the equality holdsif and only ifG≅G10n−13,n−13,n−43≅G10n−43,n−13,n−13;2n3−6n2+63n−6427,wheren≡2mod3,n≥8and the equality holdsif and only ifG≅G10n−23,n−23,n−23.Proof.
Similar to the proof of Lemma3, by Lemmas 1 and 2, direct computing yields zG10a,b,c=2abc+bc+ab+2a+3b+2c+2. By the method of Lagrange multipliers, we make auxiliary function La,b,c=λa+b+c+2−n+2abc+bc+ab+2a+3b+2c+2, where a+b+c+2=n, a,b,c≥1, and at most one of them is 1. Taking the partial derivatives of a, b, c, and λ in La,b,c,λ, we can obtain the following equations:(22)La=λ+2bc+b+2=0,Lb=λ+2ac+c+a+3=0,Lc=λ+2ab+b+2=0,Lλ=a+b+c+2−n=0,a≥1,b≥1andc≥1.
Solving the equations as above, we getb=a+1−a/a+1. Since b=a+1−a/a+1 is an integer, we know that b=⌈a+1−a/a+1⌉ or b=⌊a+1−a/a+1⌋. By b=⌈a+1−a/a+1⌉ and a+b+c+2=n, we can obtain that a=n−3/3, b=n/3, and c=n−3/3. Similarly, by b=⌊a+1−a/a+1⌋ and a+b+c+2=n, we also can obtain that a=n−2/3, b=n−2/3, and c=n−2/3. Thus, we discuss two cases as follows:Case 1:a=n−3/3, b=n/3, and c=n−3/3.Becausea=n−3/3, b=n/3, and c=n−3/3 is a unique root of (22), a=n−3/3, b=n/3, and c=n−3/3 must be the unique extreme point. Since a, b, and c are integers, we consider three subcases as follows:Subcase 1: assume thatn≡0mod3. Then a=n−3/3, b=n/3, and c=n−3/3. Thus zG10n−3/3,n/3,n−3/3=2n3−6n2+63n−54/27. It is easy to verify that zG10a,b,c<2n3−6n2+63n−54/27 when a≠n−3/3, b≠n/3, and c≠n−3/3. This implies that zG≤2n3−6n2+63n−54/27 and the equality holds if and only if G≅G10n−3/3,n/3,n−3/3.Subcase 2: suppose thatn≡1mod3. Then a=n−1/3, b=n−1/3, and c=n−4/3, or a=n−4/3, b=n−1/3, and c=n−1/3. Thus zG10n−1/3,n−1/3,n−4/3=zG10n−4/3,n−1/3,n−1/3=2n3−6n2+60n−56/27. It is easy to check that zG10a,b,c<2n3−6n2+60n−56/27 when a≠n−1/3, b≠n−1/3, and c≠n−4/3, or a≠n−4/3, b≠n−1/3, and c≠n−1/3. This implies that zG≤2n3−6n2+60n−56/27 and the equality holds iff G≅G10n−1/3,n−1/3,n−4/3≅G10n−4/3,n−1/3,n−1/3.Subcase 3: consider thatn≡2mod3. Then a=n−2/3, b=n−2/3, and c=n−2/3. Thus zG10n−2/3,n−2/3,n−2/3=2n3−6n2+63n−64/27. To simplify calculation, we know that zG10a,b,c<2n3−6n2+63n−64/27 when a≠n−2/3, b≠n−2/3, and c≠n−2/3. This implies that zG≤2n3−6n2+63n−64/27 and the equality holds iff G≅G10n−2/3,n−2/3,n−2/3.Case 2:a=n−2/3, b=n−2/3, and c=n−2/3.Similar to the proof of Case 1, becausea=n−2/3, b=n−2/3, and c=n−2/3 is a unique root of (22), a=n−2/3, b=n−2/3, and c=n−2/3 must be the unique extreme point. Since a, b, and c are integers, after taking the integer, we also consider three subcases as follows:Subcase 1: assume thatn≡0mod3. Then a=n−3/3, b=n/3, and c=n−3/3. Thus zG10n−3/3,n/3,n−3/3=2n3−6n2+63n−54/27. It is easy to verify that zG10a,b,c<2n3−6n2+63n−54/27 when a≠n−3/3, b≠n/3, and c≠n−3/3. This implies that zG≤2n3−6n2+63n−54/27 and the equality holds if and only if G≅G10n−3/3,n/3,n−3/3.Subcase 2: suppose thatn≡1mod3. Then a=n−1/3, b=n−1/3, and c=n−4/3, or a=n−4/3, b=n−1/3, and c=n−1/3. Thus zG10n−1/3,n−1/3,n−4/3=zG10n−4/3,n−1/3,n−1/3=2n3−6n2+60n−56/27. It is easy to check that zG10a,b,c<2n3−6n2+60n−56/27 when a≠n−1/3, b≠n−1/3, and c≠n−4/3, or a≠n−4/3, b≠n−1/3, and c≠n−1/3. This implies that zG≤2n3−6n2+60n−56/27 and the equality holds iff G≅G10n−1/3,n−1/3,n−4/3≅G10n−4/3,n−1/3,n−1/3.Subcase 3: consider thatn≡2mod3. Then a=n−2/3, b=n−2/3, and c=n−2/3. Thus zG10n−2/3,n−2/3,n−2/3=2n3−6n2+63n−64/27. To simplify calculation, we know that zG10a,b,c<2n3−6n2+63n−64/27 when a≠n−2/3, b≠n−2/3, and c≠n−2/3. This implies that zG≤2n3−6n2+63n−64/27 and the equality holds iff G≅G10n−2/3,n−2/3,n−2/3.Lemma 13.
LetG∈G11a,b be a graph with n vertices. Then(23)zG≤3n2−4n4,wheren≥6is even, and the equality holds iffG≅G11n−42,n−42;3n2−4n−34,wheren≥8is odd, and the equality holdsiffG≅G11n−52,n−32≅G11n−32,n−52.Proof.
Similar to the proof of Lemma3, by Lemmas 1 and 2, we get zG11a,b=3ab+5a+5b+8. By the method of Lagrange multipliers, we make an auxiliary function La,b=λa+b+4−n+3ab+5a+5b+8, where a+b+4=n, a≥1, and b≥1. Taking the partial derivatives of a,b, and λ in La,b,λ, we can obtain the following equations:(24)La=λ+3b+5=0,Lb=λ+3a+5=0,Lλ=a+b+4−n=0,a≥1andb≥1.
Solving the equations as above, we obtain thata=n−4/2 and b=n−4/2. Because n−4/2,n−4/2 is a unique stable point, n−4/2,n−4/2 must be the unique extreme point. Since a and b are integers, in the following we consider two cases.Case 1: consider thatn is even. We have a=n−4/2 and b=n−4/2. Thus zG11n−4/2,n−4/2=3n2−4n/4. To simplify calculation, we get zG11a,b<3n2−4n/4 when a≠n−4/2 and b≠n−4/2. This implies that zG≤3n2−4n/4 and the equality holds iff G≅G11n−4/2,n−4/2.Case 2: assume thatn is odd. We know that a=n−5/2 and b=n−3/2, or a=n−3/2 and b=n−5/2. Thus zG11n−5/2,n−3/2=zG11n−3/2,n−5/2=3n2−4n−3/4. It is easy to check that zG11a,b<3n2−4n−3/4 when a≠n−5/2 and b≠n−3/2, or a≠n−3/2 and b≠n−5/2. This implies that zG≤3n2−4n−3/4 and the equality holds if and only if G≅G11n−5/2,n−3/2≅G11n−3/2,n−5/2.Lemma 14.
LetG∈G12a,b be a graph with n vertices. Then(25)zG≤5n2−24n+484,wheren≥6is even, and the equality holds iffG≅G12n−42,n−42;5n2−24n+474,wheren≥7is odd, and the equality holds iffG≅G12n−32,n−52.Proof.
Similar to the proof of Lemma3, by Lemmas 1 and 2, direct computing yields zG12a,b=5ab+5a+3b+8. Using the method of Lagrange multipliers, we make auxiliary function La,b=λa+b+4−n+5ab+5a+3b+8, where a+b+4−n, a≥1, and b≥1. Taking the partial derivatives of a, b, and λ in La,b,λ, we can obtain the following equations:(26)La=λ+5b+5=0,Lb=λ+5a+3=0,Lλ=a+b+4−n=0,a≥1andb≥1.
Solving the equations as above, we geta=b+2/5. Since a=b+2/5 is an integer, we know that a=⌊b+2/5⌋ or a=⌈b+2/5⌉. By a=⌊b+2/5⌋ and a+b+4=n, we can obtain that a=n−4/2 and b=n−4/2. Similarly, by a=⌈b+2/5⌉ and a+b+4=n, we also can obtain that a=n−3/2 and b=n−5/2. So, we discuss two cases as follows:Case 1:a=n−4/2 and b=n−4/2.Becausea=n−4/2 and b=n−4/2 is a unique root of (26), a=n−4/2 and b=n−4/2 must be the unique extreme point. Since a and b are integers, we consider two subcases.Subcase 1: assume thatn is even. Then a=n−4/2 and b=n−4/2. Thus zG12n−4/2,n−4/2=5n2−24n+48/4. It is easy to verify that zG12a,b<5n2−24n+48/4 when a≠n−4/2 and b≠n−4/2. This implies that zG≤5n2−24n+48/4 and the equality holds if and only if G≅G12n−4/2,n−4/2.Subcase 2: suppose thatn is odd. We know that a=n−3/2 and b=n−5/2. Thus zG12n−3/2,n−5/2=5n2−24n+47/4. It is easy to check that zG12a,b<5n2−24n+47/4 when a≠n−3/2 and b≠n−5/2. This implies that zG≤5n2−24n+47/4 and the equality holds iff G≅G12n−3/2,n−5/2.Case 2:a=n−3/2 and b=n−5/2.Similar to the proof of Case 1, becausea=n−4/2 and b=n−4/2 is a unique root of (26), a=n−4/2 and b=n−4/2 must be the unique extreme point. Since a and b are integers, we consider two subcases.Subcase 1: assume thatn is even. Then a=n−4/2 and b=n−4/2. Thus zG12n−4/2,n−4/2=5n2−24n+48/4. It is easy to verify that zG12a,b<5n2−24n+48/4 when a≠n−4/2 and b≠n−4/2. This implies that zG≤5n2−24n+48/4 and the equality holds if and only if G≅G12n−4/2,n−4/2.Subcase 2: suppose thatn is odd. We know that a=n−3/2 and b=n−5/2. Thus zG12n−3/2,n−5/2=5n2−24n+47/4. It is easy to check that zG12a,b<5n2−24n+47/4 when a≠n−3/2 and b≠n−5/2. This implies that zG≤5n2−24n+47/4 and the equality holds iff G≅G12n−3/2,n−5/2.Lemma 15.
LetG∈G13a,b be a graph with n vertices. Then(27)zG≤n2−4n+10,wheren≥6is even, and the equality holds iffG≅G13n−42,n−42;n2−4n+9,wheren≥7is odd, and the equality holdsiffG≅G13n−32,n−52≅G13n−52,n−32.Proof.
Similar to the proof of Lemma3, by Lemmas 1 and 2, we get that zG13a,b=4ab+4a+4b+10. According to the method of Lagrange multipliers, we make an auxiliary function La,b=λa+b+4−n+4ab+4a+4b+10, where a+b+4=n, a≥1, and b≥1. Taking the partial derivatives of a,b, and λ in La,b,λ, we obtain the following equations:(28)La=λ+4b+4=0,Lb=λ+4a+4=0,Lλ=a+b+4−n=0,a≥1andb≥1.
Solving the equations as above, we obtain thata=n−4/2 and b=n−4/2. Because n−4/2,n−4/2 is a unique stable point, n−4/2,n−4/2 must be the unique extreme point. Since a and b are integers, we only consider two cases.Case 1: assume thatn is even. We obtain a=n−4/2 and b=n−4/2. Thus zG13n−4/2,n−4/2=n2−4n+10. It is easy to check that zG13a,b<n2−4n+10 when a≠n−4/2 and b≠n−4/2. This implies that zG≤n2−4n+10 and the equality holds if and only if G≅G13n−4/2,n−4/2.Case 2: consider thatn is odd. We have a=n−3/2 and b=n−5/2, or a=n−5/2 and b=n−3/2. So, zG13n−3/2,n−5/2=zG13n−5/2,n−3/2=n2−4n+9. It is easy to verify that zG13a,b<n2−4n+9 when a≠n−3/2 and b≠n−5/2, or a≠n−5/2 and b≠n−3/2. This means that zG≤n2−4n+9 and the equality holds if and only if G≅G3n−3/2,n−5/2≅G3n−5/2,n−3/2.Lemma 16.
LetG∈G14a,b be a graph with n vertices. Then(29)zG≤32n2−8n+16,wherenis even,n≥8and the equality holds iffG≅G14n−42,n−62≅G14n−62,n−42;32n2−8n+352,wherenis odd,n≥7and the equality holds iffG≅G14n−52,n−52.Proof.
Similar to the proof of Lemma3, by Lemmas 1 and 2, we obtain that zG14a,b=6ab+7a+7b+15. According to the method of Lagrange multipliers, we make an auxiliary function La,b=λa+b+5−n+6ab+7a+7b+15, where a+b+5=n, a≥1, and b≥1. Taking the partial derivatives of a,b, and λ in La,b,λ, we can obtain the following equations:(30)La=λ+6b+7=0,Lb=λ+6a+7=0,Lλ=a+b+5−n=0,a≥1andb≥1.
Solving the equations as above, we obtain thata=n−5/2 and b=n−5/2. Because n−5/2,n−5/2 is a unique stable point, n−5/2,n−5/2 must be the unique extreme point. Since a and b are integers, we only consider two cases.Case 1: consider thatn is even. We have a=n−4/2 and b=n−6/2, or a=n−6/2 and b=n−4/2. Thus zG14n−4/2,n−6/2=zG14n−6/2,n−4/2=3/2n2−8n+16. To simplify calculation, we get zG14a,b<3/2n2−8n+16 when a≠n−4/2 and b≠n−6/2, or a≠n−6/2 and b≠n−4/2. This implies that zG≤3/2n2−8n+16 and the equality holds iff G≅G14n−4/2,n−6/2≅G14n−6/2,n−4/2.Case 2: assume thatn is odd. Then a=n−5/2 and b=n−5/2. So zG14n−5/2,n−5/2=3/2n2−8n+35/2. It is easy to check that zG14a,b<3/2n2−8n+35/2 when a≠n−5/2 and b≠n−5/2. This implies that zG≤3/2n2−8n+35/2 and the equality holds if and only if G≅G14n−5/2,n−5/2.Proof of Theorem 1.
By Lemmas3–16, we know the maximum Hosoya index in Gii=1,2,…,14. Employing Mathematica 12.0 to compute the difference of the maximum Hosoya indices of Gi and Gj, it yields directly the result in Theorem 1.


## 4. Concluding Remark

In this paper, we characterize the sharp upper bound of Hosoya indices of all graphs inℬn3. Furthermore, we also determine the upper bound of every type of bicyclic graphs. There exists an interesting problem:Problem 1.
Which graphG∈ℬn3 has the minimum Hosoya index?We attempted to find a solution to the problem; however, the problem is very difficult for us.



---

*Source: 5555700-2021-09-03.xml*