Let G be a simple connected graph with the vertex set V(G) and dB(u,v) be the biharmonic distance between two vertices u and v in G. The biharmonic index BH(G) of G is defined as
BH(G)=12∑u∈V(G)∑v∈V(G)d2B(u,v)=nn∑i=21λ2i(G),
where λi(G) is the i-th eigenvalue of the Laplacian matrix of G with n vertices. In this paper, we provide the mathematical relationships between the biharmonic index and some classic topological indices: the first Zagreb index, the forgotten topological index and the Kirchhoff index. In addition, the extremal value on the biharmonic index for all graphs with diameter two, trees and firefly graphs are given, respectively. Finally, some graph operations on the biharmonic index are presented.
Citation: Zhen Lin. The biharmonic index of connected graphs[J]. AIMS Mathematics, 2022, 7(4): 6050-6065. doi: 10.3934/math.2022337
[1] | Chenxu Yang, Meng Ji, Kinkar Chandra Das, Yaping Mao . Extreme graphs on the Sombor indices. AIMS Mathematics, 2022, 7(10): 19126-19146. doi: 10.3934/math.20221050 |
[2] | Jianwei Du, Xiaoling Sun . On the graph connectivity and the variable sum exdeg index. AIMS Mathematics, 2021, 6(1): 607-622. doi: 10.3934/math.2021037 |
[3] | Edil D. Molina, José M. Rodríguez-García, José M. Sigarreta, Sergio J. Torralbas Fitz . On the Gutman-Milovanović index and chemical applications. AIMS Mathematics, 2025, 10(2): 1998-2020. doi: 10.3934/math.2025094 |
[4] | Ali N. A. Koam, Ali Ahmad, Azeem Haider, Moin A. Ansari . Computation of eccentric topological indices of zero-divisor graphs based on their edges. AIMS Mathematics, 2022, 7(7): 11509-11518. doi: 10.3934/math.2022641 |
[5] | Shabana Anwar, Muhammad Kamran Jamil, Amal S. Alali, Mehwish Zegham, Aisha Javed . Extremal values of the first reformulated Zagreb index for molecular trees with application to octane isomers. AIMS Mathematics, 2024, 9(1): 289-301. doi: 10.3934/math.2024017 |
[6] | Sumaira Hafeez, Rashid Farooq . On generalized inverse sum indeg index and energy of graphs. AIMS Mathematics, 2020, 5(3): 2388-2411. doi: 10.3934/math.2020158 |
[7] | Zhenhua Su, Zikai Tang . Extremal unicyclic and bicyclic graphs of the Euler Sombor index. AIMS Mathematics, 2025, 10(3): 6338-6354. doi: 10.3934/math.2025289 |
[8] | Ali Al Khabyah . Mathematical aspects and topological properties of two chemical networks. AIMS Mathematics, 2023, 8(2): 4666-4681. doi: 10.3934/math.2023230 |
[9] | Shama Liaqat, Zeeshan Saleem Mufti, Yilun Shang . Newly defined fuzzy Misbalance Prodeg Index with application in multi-criteria decision-making. AIMS Mathematics, 2024, 9(8): 20193-20220. doi: 10.3934/math.2024984 |
[10] | Hongzhuan Wang, Xianhao Shi, Ber-Lin Yu . On the eccentric connectivity coindex in graphs. AIMS Mathematics, 2022, 7(1): 651-666. doi: 10.3934/math.2022041 |
Let G be a simple connected graph with the vertex set V(G) and dB(u,v) be the biharmonic distance between two vertices u and v in G. The biharmonic index BH(G) of G is defined as
BH(G)=12∑u∈V(G)∑v∈V(G)d2B(u,v)=nn∑i=21λ2i(G),
where λi(G) is the i-th eigenvalue of the Laplacian matrix of G with n vertices. In this paper, we provide the mathematical relationships between the biharmonic index and some classic topological indices: the first Zagreb index, the forgotten topological index and the Kirchhoff index. In addition, the extremal value on the biharmonic index for all graphs with diameter two, trees and firefly graphs are given, respectively. Finally, some graph operations on the biharmonic index are presented.
The Laplacian matrix of a graph G, denoted by L(G), is given by L(G)=D(G)−A(G), where D(G) is the diagonal matrix of its vertex degrees and A(G) is the adjacency matrix. The Laplacian characteristic polynomial of G, is equal to det(xIn−L(G)), denoted by ϕ(L(G)). We denote λi=λi(G) the i-th smallest eigenvalue of L(G). In particular, λ2(G) and λn(G) are called the algebraic connectivity [8] and the Laplacian spectral radius of G, respectively. The Laplacian spectral ratio of a connected graph G with n vertices is defined as rL(G)=λnλ2. Barahona et al. [4] showed that a graph G exhibits better synchronizability if the ratio rL(G) is small.
The topological indices have fundamental applications in chemical disciplines [5,7,31], computational linguistics [29], computational biology [28] and etc. Let d(u,v) be the distance between vertices u and v of G. The Wiener index W(G) of a connected graph G, introduced by Wiener [35] in 1947, is defined as W(G)=∑u,v∈V(G)d(u,v), which is used to predict the boiling points of paraffins by their molecular structure. The Wiener index found numerous applications in pure mathematics and other sciences [13,21]. In 1972, Gutman and Trinajstić [18] proposed the first Zagreb index M1(G) of a graph G, and defined it as the sum of the squares of vertex degrees of G. There is a wealth of literature relating to the first Zagreb index, the readers are referred to [3,10,34] and the references therein. Recently, Furtula and Gutman [9] defined the forgotten topological index of a graph G as the sum of the cubes of vertex degrees of G, denoted by F(G). In particular, the forgotten topological index of several important chemical structures which have high frequency in drug structures is obtained [1,17]. The Kirchhoff index of a graph G is defined as the sum of resistance distances [20] between all pairs of vertices of G, denoted by Kf(G). Gutman and Mohar [15] gave an important calculation formula on Kirchhoff index, that is Kf(G)=∑ni=21λi. The Kirchhoff index is often used to measure how well connected a network is [12,20].
In 2010, Lipman, Rustamov and Funkhouser [25] proposed the biharmonic distance dB(u,v) between two vertices u and v in a graph G as follows:
d2B(u,v)=L2+uu+L2+vv−2L2+uv, |
where L2+uv is the (u,v)-entry of the matrix obtained from the square of Moore Penrose inverse of L(G). They showed that the biharmonic distance has some advantages over resistance distance and geodesic distance in computer graphics, geometric processing, shape analysis and etc. Meanwhile, They used biharmonic distance to measure the distances between pairs of points on a 3D surface, which is a fundamental problem in computer graphics and geometric processing. Moreover, the biharmonic distance as a tool is used to analyze second-order consensus dynamics with external perturbations in [37,38]. Inspired by Wiener index, Yi et al. [37] and Wei et al. [36] proposed the concept of biharmonic index of a graph G as follows:
BH(G)=12∑u∈V(G)∑v∈V(G)d2B(u,v)=nn∑i=21λ2i(G). |
Wei et al. [36] obtained a relationship between biharmonic index and Kirchhoff index and determined the unique graph having the minimum biharmonic index among the connected graphs with n vertices.
In this paper, we study the biharmonic index of connected graphs from the perspective of Mathematics. Firstly, we establish the mathematical relationships between the biharmonic index and some classic topological indices: the first Zagreb index, the forgotten topological index and the Kirchhoff index. Secondly, we study the extremal value on the biharmonic index for all graphs with diameter two, trees and firefly graphs of fixed order, around Problem 6.3 in [36]. Finally, some graph operations on the biharmonic index are presented.
Let K1,n−1, Pn and Kn denote the star, the path and the complete graph with n vertices, respectively. Let τ(G) be the number of spanning trees of a connected graph. The double star S(a,b) is the tree obtained from K2 by attaching a pendant edges to a vertex and b pendant edges to the other. A firefly graph Fs,t,n−2s−2t−1 (s≥0,t≥0,n−2s−2t−1≥0) is a graph of order n that consists of s triangles, t pendent paths of length 2 and n−2s−2t−1 pendent edges, sharing a common vertex. For v∈V(G), let Lv(G) be the principal submatrix of L(G) formed by deleting the row and column corresponding to vertex v.
Lemma 2.1. ([32]) Let X=(a1,…,an) and Y=(b1,…,bn) be two positive n-tuples. Then
(n∑i=1a2i)(n∑i=1b2i)(n∑i=1aibi)2≤(a+A)24aA, |
where a=min{aibi} and A=max{aibi} for 1≤i≤n.
Lemma 2.2. ([32]) Let X=(a1,…,an) and Y=(b1,…,bn) be two positive n-tuples. Then
(n∑i=1a2i)(n∑i=1b2i)−(n∑i=1aibi)2≤(A−a)24aA(n∑i=1aibi)2, |
where a=min{aibi} and A=max{aibi} for 1≤i≤n.
Lemma 2.3. ([33]) If ai>0, bi>0, p>0, i=1,2,…,n, then the following inequality holds:
n∑i=1ap+1ibpi≥(n∑i=1ai)p+1(n∑i=1bi)p |
with equality if and only if a1b1=a2b2=⋯=anbn.
Lemma 2.4. ([30]) Let n≥1 be an integer and a1≥a2≥⋯≥an be some non-negative real numbers. Then
(a1+an)(a1+a2+⋯+an)≥a21+a22+⋯+a2n+na1an |
Moreover, the equality holds if and only if for some r∈{1,2,…,n}, a1=⋯=ar and ar+1=⋯=an.
Lemma 2.5. ([22]) Let a1,…,an≥0. Then
n[1nn∑i=1ai−(n∏i=1ai)1n]≤Φ≤n(n−1)[n∑i=1ain−(n∏i=1ai)1n], |
where Φ=n∑ni=1ai−(∑ni=1√ai)2.
Lemma 2.6. ([23]) Let a1,a2,…,an and b1,b2,…,bn be real numbers such that a≤ai≤A and b≤bi≤B for i=1,2,…,n. Then there holds
|1nn∑i=1aibi−(1nn∑i=1ai)(1nn∑i=1bi)|≤1n⌊n2⌋(1−1n⌊n2⌋)(A−a)(B−b), |
where ⌊x⌋ denotes the integer part of x.
Lemma 2.7. ([16]) If T is a tree with diameter d(T), then λ2(T)≤2(1−cos(πd+1)).
Lemma 2.8. ([19]) The number of Laplacian eigenvalues less than the average degree 2−2n of a tree with n vertices is at least ⌈n2⌉.
Lemma 2.9. ([6]) Let G be a connected graph of diameter 2. Then λ2(G)≥1.
Lemma 2.10. ([11]) Let uv be a cut edge of a graph G. Let G−uv=G1+G2, where G1 and G2 are the components of G−uv, G1+G2 is the sum of G1 and G2, u∈V(G1) and v∈V(G2). Then
ϕ(L(G))=ϕ(L(G1))ϕ(L(G2))−ϕ(L(G1))ϕ(Lv(G2))−ϕ(Lu(G1))ϕ(L(G2)). |
In the following theorems, mathematical relations between the biharmonic index and other classic topological indices are established.
Theorem 3.1. Let G be a connected graph with n vertices and m edges. Then
BH(G)≤n(n−1)24(2m+M1(G))(rL(G)+1rL(G))2. |
Proof. In this proof we use Lemma 2.1 with ai=λi and bi=1λi for 2≤i≤n. Then a=λ22 and A=λ2n. Thus
(n∑i=2λ2i)(n∑i=21λ2i)(n−1)2≤(λ22+λ2n)24λ22λ2n, |
Since ∑ni=2λ2i=2m+M1(G), we have
(2m+M1(G))BH(G)n(n−1)2≤(λ22+λ2n)24λ22λ2n, |
that is,
BH(G)≤n(n−1)24(2m+M1(G))(λ2λn+λnλ2)2. |
This completes the proof.
Theorem 3.2. Let G be a connected graph with n vertices and m edges. Then
BH(G)≤n(n−1)24(2m+M1(G))(4+(rL(G)−1rL(G))2). |
Proof. In this proof we use Lemma 2.2 with ai=λi and bi=1λi for 2≤i≤n. Then a=λ22 and A=λ2n. Thus
(n∑i=2λ2i)(n∑i=21λ2i)−(n−1)2≤(λ2n−λ22)24λ22λ2n(n−1)2. |
Since ∑ni=2λ2i=2m+M1(G), we have
2m+M1(G)nBH(G)−(n−1)2≤(λ2n−λ22)24λ22λ2n(n−1)2, |
that is,
BH(G)≤n(n−1)24(2m+M1(G))(4+(λnλ2−λ2λn)2). |
This completes the proof.
Theorem 3.3. Let p be a positive real number and G be a connected graph with n vertices and m edges. Then
BH(G)≥n((2m)p+1n∑i=2λ3p+1i)1p |
with equality if and only if G≅Kn.
Proof. In this proof we use Lemma 2.3 with ai=λi and bi=1λ2i for 2≤i≤n. Then we have
n∑i=2λ3p+1i≥(n∑i=2λi)p+1(n∑i=21λ2i)p. |
Since ∑ni=2λi=2m, we have
BH(G)≥n((2m)p+1n∑i=2λ3p+1i)1p |
with equality if and only if λ32=⋯=λ3n, that is G≅Kn. This completes the proof.
Corollary 3.4. Let G be a connected graph with n vertices and m edges. Then
BH(G)≥16nm4[2m+M1(G)]3 |
with equality if and only if G≅Kn.
Proof. Let p=13. Since ∑ni=2λ2i=2m+M1(G), by Theorem 3.3, we have
BH(G)≥n((2m)4/3n∑i=2λ2i)3=16nm4[2m+M1(G)]3 |
with equality if and only if G≅Kn. This completes the proof.
Corollary 3.5. Let G be a connected graph with n vertices, m edges and t(G) triangles. Then
BH(G)≥√32n2m5[3M1(G)+F(G)+6t(G)]3 |
with equality if and only if G≅Kn.
Proof. Let p=23. Since ∑ni=2λ3i=3M1(G)+F(G)+6t(G), by Theorem 3.3, we have
BH(G)≥n((2m)5/3n∑i=2λ3i)3/2=√32n2m5[3M1(G)+F(G)+6t(G)]3 |
with equality if and only if G≅Kn. This completes the proof.
In this section, we establish relationship between biharmonic index and Kirchhoff index based on the algebraic connectivity, the Laplacian spectral radius and the number of spanning trees.
Theorem 4.1. Let G be a connected graph with n vertices. Then
BH(G)≤(1λ2+1λn)Kf(G)−n(n−1)1λ2λn |
with equality if and only if for some r∈{2,…,n}, λ2=⋯=λr and λr+1=⋯=λn.
Proof. By Lemma 2.4, we have
(1λ2+1λn)(1λ2+⋯+1λn)≥1λ22+⋯+1λ2n+(n−1)1λ2λn, |
that is,
n(1λ2+1λn)(1λ2+⋯+1λn)≥n(1λ22+⋯+1λ2n)+n(n−1)1λ2λn, |
that is,
(1λ2+1λn)Kf(G)≥nBH(G)+n(n−1)1λ2λn, |
that is,
BH(G)≤(1λ2+1λn)Kf(G)−n(n−1)1λ2λn |
with equality if and only if for some r∈{2,…,n}, λ2=⋯=λr and λr+1=⋯=λn. This completes the proof.
Theorem 4.2. Let G be a connected graph with n≥3 vertices. Then
Kf2(G)n(n−2)−n(n−1)n−2(1nτ(G))2n−1≤BH(G)≤Kf2(G)n−n(n−1)(n−2)(1nτ(G))2n−1. |
Proof. In this proof we use Lemma 2.5 with ai=1λ2i for 2≤i≤n. Then we have
(n−1)[1n−1n∑i=21λ2i−(n∏i=21λ2i)1n−1]≤Φ≤(n−1)(n−2)[n∑i=21λ2in−1−(n∏i=21λ2i)1n−1], |
where Φ=(n−1)∑ni=21λ2i−(∑ni=2√1λ2i)2=n−1nBH(G)−1n2Kf2(G). Since ∏ni=2λi=nτ(G), we have
1nBH(G)−(n−1)(1nτ(G))2n−1≤Φ≤n−2nBH(G)−(n−1)(n−2)(1nτ(G))2n−1, |
where Φ=n−1nBH(G)−1n2Kf2(G). Thus we have
Kf2(G)n(n−2)−n(n−1)n−2(1nτ(G))2n−1≤BH(G)≤Kf2(G)n−n(n−1)(n−2)(1nτ(G))2n−1. |
This completes the proof.
Theorem 4.3. Let G be a connected graph with n vertices. Then
|n(n−1)BH(G)−Kf2(G)|≤n2(n−1)24(1−1+(−1)n+12n2)(1λ2−1λn)2. |
Proof. In this proof we use Lemma 2.6 with ai=bi=1λi for 2≤i≤n. Then we have
|1n−1n∑i=21λ2i−1(n−1)2n∑i=21λi|≤1n⌊n2⌋(1−1n⌊n2⌋)(1λ2−1λn)2, |
that is,
|n(n−1)BH(G)−Kf2(G)|≤n(n−1)2⌊n2⌋(1−1n⌊n2⌋)(1λ2−1λn)2. |
Note that ⌊n2⌋(1−1n⌊n2⌋)=n4(1−1+(−1)n+12n2). We have
|n(n−1)BH(G)−Kf2(G)|≤n2(n−1)24(1−1+(−1)n+12n2)(1λ2−1λn)2. |
This completes the proof.
In this section, we study the extremal value on the biharmonic index for trees and firefly graphs of fixed order. Moreover, we show that the star is the unique graph with maximum biharmonic index among all graphs on diameter two.
Theorem 5.1. Let S(a,b) be a double star tree on n vertices and a+b=n−2. Then
n2+3n+4n−16≤BH(S(a,b))≤n2−2n+4⌈n−22⌉⌊n−22⌋+(⌈n−22⌉⌊n−22⌋+1)2n, |
the left (right) equality holds if and only if S(1,n−3) (S(⌈n−22⌉,⌊n−22⌋).
Proof. By direct calculation, we have
ϕ(L(S(a,b)))=x(x−1)n−4[x3−(n+2)x2+(2n+ab+1)x−n]. |
Let x1, x2 and x3 be the roots of the following polynomial
f(x):=x3−(n+2)x2+(2n+ab+1)x−n. |
By the Vieta Theorem, we have
{x1+x2+x3=n+2,1x1+1x2+1x3=2n+ab+1n,x1x2x3=n. |
Thus
1x21+1x22+1x23=(1x1+1x2+1x3)2−2(1x1x2+1x2x3+1x1x3)=(1x1+1x2+1x3)2−2n(x1+x2+x3)=(2n+ab+1n)2−2n(n+2)=(2n+ab+1n)2−4n−2. |
Further, we have
BH(S(a,b))=nn∑i=21λ2i=n(n−4)+2n+4ab+(ab+1)2n=n2−2n+4ab+(ab+1)2n. |
Since n−3≤ab≤⌈n−22⌉⌊n−22⌋, we have
n2+3n+4n−16≤BH(S(a,b))≤n2−2n+4⌈n−22⌉⌊n−22⌋+(⌈n−22⌉⌊n−22⌋+1)2n, |
the left (right) equality holds if and only if S(1,n−3) (S(⌈n−22⌉,⌊n−22⌋). This completes the proof.
Theorem 5.2. Let Tn be a tree on n≥8 vertices. If the diameter d(Tn)≥π4√7n8−1, then
BH(Tn)>BH(K1,n−1). |
Proof. Since 1−cosx<x22, by Lemma 2.7, we have
λ2(Tn)≤2(1−cos(πd(Tn)+1))<(πd(Tn)+1)2. |
By Lemma 2.8, we have
BH(Tn)=n(1λ22+⋯+1λ2n)>n((d(Tn)+1)4π4+(⌈n2⌉−2)1(2−2n)2+⌊2n⌋1n2)>n((d(Tn)+1)4π4+(n2−2)1(2−2n)2+(2n−1)1n2)=n((d(Tn)+1)4π4+n2(n−4)8(n−1)2+(2n−1)1n2)≥n(7n8+n2(n−4)8(n−1)2+(2n−1)1n2)>n(n−1)>n(n−2+1n2)=BH(K1,n−1) |
for n≥8. This completes the proof.
The following conjecture is concretization of Problem 6.3 in [36].
Conjecture 5.3. Let Tn be a tree on n≥5 vertices. Then
BH(K1,n−1)≤BH(Tn)≤BH(Pn), |
the left (right) equality holds if and only if Tn=K1,n−1 (Tn=Pn).
Theorem 5.4. Let G be a connected graph with n vertices and diameter d(G)=2. Then
BH(G)≤BH(K1,n−1) |
with equality if and only if G=K1,n−1.
Proof. It is well known that λn≥Δ+1 and λn−1≥Δ2 (see [14,24]), where Δ and Δ2 are the maximum degree and the second largest degree of G, respectively. If 2≤Δ2≤Δ, by Lemma 2.9, we have
BH(G)=n(1λ22+⋯+1λ2n)≤n(n−3+1Δ22+1(Δ+1)2)<n(n−3+122+1(2+1)2)<n(n−2+1n2)=BH(K1,n−1). |
Thus Δ2=1, that is, G=K1,n−1, then BH(G)=BH(K1,n−1).
Combining the above arguments, we have BH(G)≤BH(K1,n−1) with equality if and only if G=K1,n−1. This completes the proof.
Theorem 5.5. Let Fs,t,n−2s−2t−1 (s≥0,t≥0,n−2s−2t−1≥0) be a firefly graph with n≥7 vertices.
(1) If s=t=0, then BH(F0,0,n−1)=n2−2n+1n.
(2) If s=0 and t=1, then BH(F0,1,n−3)=n2+3n−16+4n.
(3) If s=0, t≥2 and n is odd, then
n2+8n+25n−32≤BH(F0,t,n−2t−1)≤7n22−41n4+254n+12, |
the left (right) equality holds if and only if F0,t,n−2t−1=F0,2,n−5 (F0,t,n−2t−1=F0,n−12,0).
If s=0, t≥2 and n is even, then
n2+8n+25n−32≤BH(F0,t,n−2t−1)≤7n22−51n4+16n+4, |
the left (right) equality holds if and only if F0,t,n−2t−1=F0,2,n−5 (F0,t,n−2t−1=F0,n−22,1).
(4) If s≥1, t=0 and n is odd, then
5n29−14n9+1n≤BH(F0,t,n−2t−1)≤n2−269n+1n, |
the left (right) equality holds if and only if Fs,0,n−2s−1=F1,0,n−3 (Fs,0,n−2s−1=Fn−12,0,0).
If s≥1, t=0 and n is even, then
5n29−10n9+1n≤BH(F0,t,n−2t−1)≤n2−269n+1n, |
the left (right) equality holds if and only if Fs,0,n−2s−1=F1,0,n−3 (Fs,0,n−2s−1=Fn−22,0,1).
(5) If s≥1, t≥1 and n is odd, then
5n29+13n3+4n−16≤BH(Fs,t,n−2s−2t−1)≤7n22−581n36+1214n+152, |
the left (right) equality holds if and only if Fs,t,n−2s−2t−1=Fn−32,1,0 (Fs,t,n−2s−2t−1=F1,n−32,0).
If s≥1, t≥1 and n is even, then
5n29+43n9+4n−16≤BH(Fs,t,n−2s−2t−1)≤7n22−671n36+49n+11, |
the left (right) equality holds if and only if Fs,t,n−2s−2t−1=Fn−42,1,1 (Fs,t,n−2s−2t−1=F1,n−42,1).
Proof. (1) If s=t=0, then F0,0,n−1≅K1,n−1. Thus BH(F0,0,n−1)=n2−2n+1n.
(2) If s=0 and t=1, by Lemma 2.10, we have
ϕ(L(F0,1,n−3))=ϕ(L(K1,n−3))ϕ(L(P2))−(x−1)n−3ϕ(L(P2))−(x−1)ϕ(L(K1,n−3))=x2(x−2)(x−n+2)(x−1)n−4−x(x−2)(x−1)n−3−x(x−n+2)(x−1)n−3=x(x−1)n−4[x3−(n+2)x2+(3n−2)x−n]. |
By a similar reasoning as the proof of Theorem 5.1, we have
BH(F0,1,n−3)=n2+3n−16+4n. |
(3) If s=0 and t≥2, then we have
ϕ(L(F0,t,n−2t−1))=x(x−1)n−2t−2(x2−3x+1)t−1[x3−(n−t+3)x2+(3n−3t+1)x−n]. |
By a similar reasoning as the proof of Theorem 5.1, we have
BH(F0,t,n−2t−1)=n2+5tn−11n+2t+(3n−3t+1)2n−6=n2−2n+9t2+(5n2−16n−6)t+1n. |
If 2≤t≤n−12 for odd n, we have
n2+8n+25n−32≤BH(F0,t,n−2t−1)≤7n22−41n4+254n+12, |
the left (right) equality holds if and only if F0,t,n−2t−1=F0,2,n−5 (F0,t,n−2t−1=F0,n−12,0). If 2≤t≤n−22 for even n, we have
n2+8n+25n−32≤BH(F0,t,n−2t−1)≤7n22−51n4+16n+4, |
the left (right) equality holds if and only if F0,t,n−2t−1=F0,2,n−5 (F0,t,n−2t−1=F0,n−22,1).
(4) If s≥1 and t=0, by Lemma 2.10, we have
ϕ(L(Fs,0,n−2s−1))=x(x−n)(x−3)s(x−1)n−s−2. |
Thus
BH(Fs,0,n−2s−1)=n2−89sn−2n+1n. |
If 1≤s≤n−12 for odd n, we have
5n29−14n9+1n≤BH(F0,t,n−2t−1)≤n2−269n+1n, |
the left (right) equality holds if and only if Fs,0,n−2s−1=F1,0,n−3 (Fs,0,n−2s−1=Fn−12,0,0). If 1≤s≤n−22 for even n, we have
5n29−10n9+1n≤BH(F0,t,n−2t−1)≤n2−269n+1n, |
the left (right) equality holds if and only if Fs,0,n−2s−1=F1,0,n−3 (Fs,0,n−2s−1=Fn−22,0,1).
(5) If s≥1 and t≥1, by Lemma 2.10, we have
ϕ(L(Fs,t,n−2s−2t−1))=x(x−3)s(x−1)n−s−2t−2(x2−3x+1)t−1[x3−(n−t+3)x2+(3n−3t+1)x−n]. |
By a similar reasoning as the proof of Theorem 5.1, we have
BH(L(Fs,t,n−2s−2t−1))=n2−89sn−2n+9t2+(5n2−16n−6)t+1n. |
If s=1 and t=n−32 for odd n, we have
BH(Fs,t,n−2s−2t−1)max=7n22−581n36+1214n+152, |
the equality holds if and only if Fs,t,n−2s−2t−1=F1,n−32,0.
If s=1 and t=n−42 for even n, we have
BH(Fs,t,n−2s−2t−1)max=7n22−671n36+49n+11, |
the equality holds if and only if Fs,t,n−2s−2t−1=F1,n−42,1.
If s=n−32 and t=1 for odd n, we have
BH(Fs,t,n−2s−2t−1)min=5n29+13n3+4n−16, |
the equality holds if and only if Fs,t,n−2s−2t−1=Fn−32,1,0.
If s=n−42 and t=1 for even n, we have
BH(Fs,t,n−2s−2t−1)min=5n29+43n9+4n−16, |
the equality holds if and only if Fs,t,n−2s−2t−1=Fn−42,1,1.
Combining the above arguments, we have the proof.
Lemma 6.1. ([26]) Let G be a connected graph with n vertices. Then λi(¯G)=n−λn+2−i(G) for i=2,…,n.
Theorem 6.2. Let G be a connected graph with n vertices. If ¯G is a connected graph, then
BH(¯G)=nn∑i=21(n−λn+2−i(G))2. |
Proof. By Lemma 6.1, we have the proof.
The union of two graphs G1 and G2 is the graph G1∪G2 with vertex set V1(G)∪V2(G) and edge set E(G1)∪E(G2). The join G1∨G2 is obtained from G1∪G2 by adding to it all edges between vertices from V(G1) and V(G2).
Lemma 6.3. ([27]) Let G1 and G2 be graphs on n1 and n2 vertices, respectively. Then the Laplacian eigenvalues of G1∨G2 are n1+n2, λi(G1)+n2 (2≤i≤n1) and λj(G2)+n1 (2≤j≤n1).
Theorem 6.4. Let G be a connected graph with n vertices. Then
BH(G1∨G2)=(n1+n2)(1(n1+n2)2+n1∑i=21(λi(G1)+n2)2+n2∑j=21(λj(G2)+n1)2). |
Proof. By Lemma 6.3, we have the proof.
The Cartesian product of G1 and G2 is the graph G1◻G2, whose vertex set is V=V1×V2 and where two vertices (ui,vs) and (uj,vt) are adjacent if and only if either ui=uj and vsvt∈E(G2) or vs=vt and uiuj∈E(G1).
Lemma 6.5. ([8,26]) Let G1 and G2 be graphs on n1 and n2 vertices, respectively. Then the Laplacian eigenvalues of G1◻G2 are all possible sums λi(G1)+λj(G2), 1≤i≤n1 and 1≤j≤n2.
Theorem 6.6. Let G1 and G2 be two connected graphs. Then
BH(G1◻G2)=n1n2(n1∑i=21λ2i(G1)+n2∑j=21λ2j(G2)+n1∑i=2n2∑j=21(λi(G1)+λj(G2))2). |
Proof. By Lemma 6.5, we have the proof.
The lexicographic product G1[G2], in which vertices (ui,vs) and (uj,vt) are adjacent if either uiuj∈E(G1) or ui=uj and vsvt∈E(G2) (see [2]).
Lemma 6.7. ([2]) Let G1 and G2 be graphs on n1 and n2 vertices, respectively. Then the Laplacian eigenvalues of G1[G2] are n2λi(G1) and λj(G2)+d(ui)n2, where d(ui) is vertex degree of G1, 1≤i≤n1 and 2≤j≤n2.
Theorem 6.8. Let G1 and G2 be connected graphs on n1 and n2 vertices, respectively.
BH(G1[G2])=n1n2(n1∑i=21n22λ2i(G1)+n2∑j=2n1∑i=11(λj(G2)+dG1(ui)n2)2). |
Proof. By Lemma 6.7, we have the proof.
We study the biharmonic index from three aspects: the mathematical relationships between the biharmonic index and some classic topological indices, the extremal value on the biharmonic index for some special graph classes, and some graph operations on the biharmonic index. On the basis of the biharmonic distance, the biharmonic eccentricity εb(u) of vertex u in a connected graph G is defined as εb(u)=max{dB(u,v)∣v∈V(G)}. Let d(u) be the degree of the corresponding vertex u. The following four topological indices will be the problems that need further exploration.
(1) The Schultz biharmonic index:
SBI(G)=12∑u∈V(G)∑v∈V(G)(d(u)+d(v))d2B(u,v). |
(2) The Gutman biharmonic index:
GBI(G)=12∑u∈V(G)∑v∈V(G)(d(u)d(v))d2B(u,v). |
(3) The eccentric biharmonic distance sum:
ξB(G)=12∑u∈V(G)∑v∈V(G)(ε2b(u)+ε2b(v))d2B(u,v). |
(4) The multiplicative eccentricity biharmonic distance:
ξ∗B(G)=12∑u∈V(G)∑v∈V(G)(ε2b(u)ε2b(v))d2B(u,v). |
The author is grateful to the anonymous referee for careful reading and valuable comments which result in an improvement of the original manuscript. This work was supported by the National Natural Science Foundation of China (No. 12071411) and Qinghai Provincial Natural Science Foundation (No. 2021-ZJ-703).
The authors declare no conflict of interest.
[1] |
M. S. Alsharafi, M. M. Shubatah, A. Q. Alameri, The forgotten index of complement graph operations and its applications of molecular graph, Open J. Discret. Appl. Math., 3 (2020), 53–61. https://doi.org/10.30538/psrp-odam2020.0043 doi: 10.30538/psrp-odam2020.0043
![]() |
[2] | S. Barik, R. B. Bapat, S. Pati, On the Laplacian spectra of product graphs, Appl. Anal. Discrete Math., 9 (2015), 39–58. |
[3] | B. Borovićanin, K. C. Das, B. Furtula, I. Gutman, Bounds for Zagreb indices, MATCH Commun. Math. Comput. Chem., 78 (2017), 17–100. |
[4] |
M. Barahona, L. M. Pecora, Synchronization in small-world systems, Phys. Rev. Lett., 89 (2002), 054101. https://doi.org/10.1103/PhysRevLett.89.054101 doi: 10.1103/PhysRevLett.89.054101
![]() |
[5] | M. V. Diudea, QSPR/QSAR Studies by molecular descriptors, Huntington: Nova, 2001. |
[6] |
K. C. Das, Proof of conjectures involving algebraic connectivity of graphs, Linear Algebra Appl., 438 (2013), 3291–3302. https://doi.org/10.1016/j.laa.2012.11.036 doi: 10.1016/j.laa.2012.11.036
![]() |
[7] | J. Devillers, A. T. Balaban, Topological indices and related descriptors in QSAR and QSPR, Amsterdam: Gordon and Breach, 1999. |
[8] | M. Fiedler, Algebraic connectivity of graphs, Czech. Math. J., 23 (1973), 298–305. |
[9] |
B. Furtula, I. Gutman, A forgotten topological index, J. Math. Chem., 53 (2015), 1184–1190. https://doi.org/10.1007/s10910-015-0480-z doi: 10.1007/s10910-015-0480-z
![]() |
[10] | G. H. Fath-Tabar, Old and new Zagreb indices of graphs, MATCH Commun. Math. Comput. Chem., 65 (2011), 79–84. |
[11] |
J. M. Guo, On the second largest Laplacian eigenvalue of trees, Linear Algebra Appl., 404 (2005), 251–261. https://doi.org/10.1016/j.laa.2005.02.031 doi: 10.1016/j.laa.2005.02.031
![]() |
[12] |
A. Ghosh, S. Boyd, A. Saberi, Minimizing effective resistance of a graph, SIAM Rev., 50 (2008), 37–66. https://doi.org/10.1137/050645452 doi: 10.1137/050645452
![]() |
[13] | I. Gutman, S. A Klavžar, B. Mohar, Fifty years of the Wiener index, MATCH Commun. Math. Comput. Chem., 1997, 1–259. |
[14] |
R. Grone, R. Merris, The Laplacian spectrum of a graph Ⅱ, SIAM J. Discrete Math., 7 (1994), 221–229. https://doi.org/10.1137/S0895480191222653 doi: 10.1137/S0895480191222653
![]() |
[15] |
I. Gutman, B. Mohar, The quasi-Wiener and the Kirchhoff indices coincide, J. Chem. Inf. Comput. Sci., 36 (1996), 982–985. https://doi.org/10.1021/ci960007t doi: 10.1021/ci960007t
![]() |
[16] |
R. Grone, R. Merris, V. S. Sunder, The Laplacian spectral of graphs, SIAM J. Matrix Anal. Appl., 11 (1990), 218–238. https://doi.org/10.1137/0611016 doi: 10.1137/0611016
![]() |
[17] |
W. Gao, M. K. Siddiqui, M. Imran, M. K. Jamil, M. R. Farahani, Forgotten topological index of chemical structure in drugs, Saudi Pharm. J., 24 (2016), 258–264. https://doi.org/10.1016/j.jsps.2016.04.012 doi: 10.1016/j.jsps.2016.04.012
![]() |
[18] |
I. Gutman, N. Trinajstić, Graph theory and molecular orbitals. Total p-electron energy of alternant hydrocarbons, Chem. Phys. Lett., 17 (1972), 535–538. https://doi.org/10.1016/0009-2614(72)85099-1 doi: 10.1016/0009-2614(72)85099-1
![]() |
[19] |
D. P. Jacobs, E. R. Oliveira, V. Trevisan, Most Laplacian eigenvalues of a tree are small, J. Comb. Theory B, 146 (2021), 1–33. https://doi.org/10.1016/j.jctb.2020.07.003 doi: 10.1016/j.jctb.2020.07.003
![]() |
[20] |
D. J. Klein, M. Randić, Resistance distance, J. Math. Chem., 12 (1993), 81–95. https://doi.org/10.1007/BF01164627 doi: 10.1007/BF01164627
![]() |
[21] |
M. Knor, R. Škrekovski, A. Tepeh, Mathematical aspects of Wiener index, Ars Math. Contemp., 11 (2016), 327–352. https://doi.org/10.26493/1855-3974.795.ebf doi: 10.26493/1855-3974.795.ebf
![]() |
[22] |
J. X. Li, J. M. Guo, W. C. Shiu, S. B. B. Altinda, D. Bozkurt, Bounding the sum of powers of normalized Laplacian eigenvalues of a graph, Appl. Math. Comput., 324 (2018), 82–92. https://doi.org/10.1016/j.amc.2017.12.003 doi: 10.1016/j.amc.2017.12.003
![]() |
[23] |
X. Li, R. N. Mohapatra, R. S. Rodriguez, Grüss-type inequalities, J. Math. Anal. Appl., 267 (2002), 434–443. https://doi.org/10.1006/jmaa.2001.7565 doi: 10.1006/jmaa.2001.7565
![]() |
[24] |
J. S. Li, Y. L. Pan, A note on the second largest eigenvalue of the Laplacian matrix of a graph, Linear Multilinear A, 48 (2000), 117–121. https://doi.org/10.1080/03081080008818663 doi: 10.1080/03081080008818663
![]() |
[25] |
Y. Lipman, R. M. Rustamov, T. A. Funkhouser, Biharmonic distance, ACM T. Graphic, 29 (2010), 1–11. https://doi.org/10.1145/1805964.1805971 doi: 10.1145/1805964.1805971
![]() |
[26] |
R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl., 197–198 (1994), 143–176. https://doi.org/10.1016/0024-3795(94)90486-3 doi: 10.1016/0024-3795(94)90486-3
![]() |
[27] |
R. Merris, Laplacian graph eigenvectors, Linear Algebra Appl., 278 (1998), 221–236. https://doi.org/10.1016/S0024-3795(97)10080-5 doi: 10.1016/S0024-3795(97)10080-5
![]() |
[28] |
L. A. J. Müller, K. G. Kugler, M. Netzer, A. Graber, M. Dehmer, A network-based approach to classify the three domains of life, Biol. Direct, 6 (2011), 53. https://doi.org/10.1186/1745-6150-6-53 doi: 10.1186/1745-6150-6-53
![]() |
[29] |
A. Mehler, A. Lücking, P. Wei, A network model of interpersonal alignment in dialog, Entropy, 12 (2010), 1440–1483. https://doi.org/10.3390/e12061440 doi: 10.3390/e12061440
![]() |
[30] |
M. R. Oboudi, A new lower bound for the energy of graphs, Linear Algebra Appl., 580 (2019), 384–395. https://doi.org/10.1016/j.laa.2019.06.026 doi: 10.1016/j.laa.2019.06.026
![]() |
[31] | T. Puzyn, J. Leszczynski, M. T. D. Cronin, Recent advances in QSAR studies-methods and applications, Dordrecht: Springer, 2010. |
[32] | G. Pólya, Aufgaben und Lehrsütze ans der analysis, Band I: Reihen, Integralrechnung, Funktiontheorie (in German), Berlin: Springer Verlag, 1970. |
[33] | J. Radon, Über die absolut additiven mengenfunktionen, Wiener-Sitzungsber, 122 (1913), 1295–1438. |
[34] |
S. D. Stankov, M. M. Matejić, I. Ž. Milovanović, E. I. Milovanović, Ș. B. B. Altındağ, Some new bounds on the first Zagreb index, Electron. J. Math., 1 (2021), 101–107. https://doi.org/10.47443/ejm.2021.0014 doi: 10.47443/ejm.2021.0014
![]() |
[35] |
H. Wiener, Structural determination of paraffin boiling point, J. Amer. Chem. Soc., 69 (1947), 17–20. https://doi.org/10.1021/ja01193a005 doi: 10.1021/ja01193a005
![]() |
[36] | Y. L. Wei, R. H. Li, W. H. Yang, Biharmonic distance of graphs, arXiv: 2110.02656. |
[37] | Y. H. Yi, B. L. Yang, Z. Z. Zhang, S. Patterson, Biharmonic distance and the performance of second-order consensus networks with stochastic disturbances, 2018 Annual American Control Conference (ACC), 2018, 4943–4950. https://doi.org/10.23919/ACC.2018.8431294 |
[38] |
Z. B. Zhang, W. Y. Xu, Y. H. Yi, Z. Z. Zhang, Fast approximation of coherence for second-order noisy consensus networks, IEEE T. Cybernetics, 52 (2022), 677–686. https://doi.org/10.1109/TCYB.2020.2965586 doi: 10.1109/TCYB.2020.2965586
![]() |