Research article

The biharmonic index of connected graphs

  • Received: 19 October 2021 Revised: 07 January 2022 Accepted: 12 January 2022 Published: 17 January 2022
  • MSC : 05C05, 05C09, 05C35, 05C50, 05C76

  • 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)=12uV(G)vV(G)d2B(u,v)=nni=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

    Related Papers:

    [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)=12uV(G)vV(G)d2B(u,v)=nni=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(xInL(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,vV(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+vv2L2+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)=12uV(G)vV(G)d2B(u,v)=nni=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,n1, 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,n2s2t1 (s0,t0,n2s2t10) is a graph of order n that consists of s triangles, t pendent paths of length 2 and n2s2t1 pendent edges, sharing a common vertex. For vV(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

    (ni=1a2i)(ni=1b2i)(ni=1aibi)2(a+A)24aA,

    where a=min{aibi} and A=max{aibi} for 1in.

    Lemma 2.2. ([32]) Let X=(a1,,an) and Y=(b1,,bn) be two positive n-tuples. Then

    (ni=1a2i)(ni=1b2i)(ni=1aibi)2(Aa)24aA(ni=1aibi)2,

    where a=min{aibi} and A=max{aibi} for 1in.

    Lemma 2.3. ([33]) If ai>0, bi>0, p>0, i=1,2,,n, then the following inequality holds:

    ni=1ap+1ibpi(ni=1ai)p+1(ni=1bi)p

    with equality if and only if a1b1=a2b2==anbn.

    Lemma 2.4. ([30]) Let n1 be an integer and a1a2an 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,,an0. Then

    n[1nni=1ai(ni=1ai)1n]Φn(n1)[ni=1ain(ni=1ai)1n],

    where Φ=nni=1ai(ni=1ai)2.

    Lemma 2.6. ([23]) Let a1,a2,,an and b1,b2,,bn be real numbers such that aaiA and bbiB for i=1,2,,n. Then there holds

    |1nni=1aibi(1nni=1ai)(1nni=1bi)|1nn2(11nn2)(Aa)(Bb),

    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(1cos(πd+1)).

    Lemma 2.8. ([19]) The number of Laplacian eigenvalues less than the average degree 22n 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 Guv=G1+G2, where G1 and G2 are the components of Guv, G1+G2 is the sum of G1 and G2, uV(G1) and vV(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(n1)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 2in. Then a=λ22 and A=λ2n. Thus

    (ni=2λ2i)(ni=21λ2i)(n1)2(λ22+λ2n)24λ22λ2n,

    Since ni=2λ2i=2m+M1(G), we have

    (2m+M1(G))BH(G)n(n1)2(λ22+λ2n)24λ22λ2n,

    that is,

    BH(G)n(n1)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(n1)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 2in. Then a=λ22 and A=λ2n. Thus

    (ni=2λ2i)(ni=21λ2i)(n1)2(λ2nλ22)24λ22λ2n(n1)2.

    Since ni=2λ2i=2m+M1(G), we have

    2m+M1(G)nBH(G)(n1)2(λ2nλ22)24λ22λ2n(n1)2,

    that is,

    BH(G)n(n1)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+1ni=2λ3p+1i)1p

    with equality if and only if GKn.

    Proof. In this proof we use Lemma 2.3 with ai=λi and bi=1λ2i for 2in. Then we have

    ni=2λ3p+1i(ni=2λi)p+1(ni=21λ2i)p.

    Since ni=2λi=2m, we have

    BH(G)n((2m)p+1ni=2λ3p+1i)1p

    with equality if and only if λ32==λ3n, that is GKn. 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 GKn.

    Proof. Let p=13. Since ni=2λ2i=2m+M1(G), by Theorem 3.3, we have

    BH(G)n((2m)4/3ni=2λ2i)3=16nm4[2m+M1(G)]3

    with equality if and only if GKn. 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 GKn.

    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/3ni=2λ3i)3/2=32n2m5[3M1(G)+F(G)+6t(G)]3

    with equality if and only if GKn. 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(n1)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+(n1)1λ2λn,

    that is,

    n(1λ2+1λn)(1λ2++1λn)n(1λ22++1λ2n)+n(n1)1λ2λn,

    that is,

    (1λ2+1λn)Kf(G)nBH(G)+n(n1)1λ2λn,

    that is,

    BH(G)(1λ2+1λn)Kf(G)n(n1)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 n3 vertices. Then

    Kf2(G)n(n2)n(n1)n2(1nτ(G))2n1BH(G)Kf2(G)nn(n1)(n2)(1nτ(G))2n1.

    Proof. In this proof we use Lemma 2.5 with ai=1λ2i for 2in. Then we have

    (n1)[1n1ni=21λ2i(ni=21λ2i)1n1]Φ(n1)(n2)[ni=21λ2in1(ni=21λ2i)1n1],

    where Φ=(n1)ni=21λ2i(ni=21λ2i)2=n1nBH(G)1n2Kf2(G). Since ni=2λi=nτ(G), we have

    1nBH(G)(n1)(1nτ(G))2n1Φn2nBH(G)(n1)(n2)(1nτ(G))2n1,

    where Φ=n1nBH(G)1n2Kf2(G). Thus we have

    Kf2(G)n(n2)n(n1)n2(1nτ(G))2n1BH(G)Kf2(G)nn(n1)(n2)(1nτ(G))2n1.

    This completes the proof.

    Theorem 4.3. Let G be a connected graph with n vertices. Then

    |n(n1)BH(G)Kf2(G)|n2(n1)24(11+(1)n+12n2)(1λ21λn)2.

    Proof. In this proof we use Lemma 2.6 with ai=bi=1λi for 2in. Then we have

    |1n1ni=21λ2i1(n1)2ni=21λi|1nn2(11nn2)(1λ21λn)2,

    that is,

    |n(n1)BH(G)Kf2(G)|n(n1)2n2(11nn2)(1λ21λn)2.

    Note that n2(11nn2)=n4(11+(1)n+12n2). We have

    |n(n1)BH(G)Kf2(G)|n2(n1)24(11+(1)n+12n2)(1λ21λ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=n2. Then

    n2+3n+4n16BH(S(a,b))n22n+4n22n22+(n22n22+1)2n,

    the left (right) equality holds if and only if S(1,n3) (S(n22,n22).

    Proof. By direct calculation, we have

    ϕ(L(S(a,b)))=x(x1)n4[x3(n+2)x2+(2n+ab+1)xn].

    Let x1, x2 and x3 be the roots of the following polynomial

    f(x):=x3(n+2)x2+(2n+ab+1)xn.

    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)22(1x1x2+1x2x3+1x1x3)=(1x1+1x2+1x3)22n(x1+x2+x3)=(2n+ab+1n)22n(n+2)=(2n+ab+1n)24n2.

    Further, we have

    BH(S(a,b))=nni=21λ2i=n(n4)+2n+4ab+(ab+1)2n=n22n+4ab+(ab+1)2n.

    Since n3abn22n22, we have

    n2+3n+4n16BH(S(a,b))n22n+4n22n22+(n22n22+1)2n,

    the left (right) equality holds if and only if S(1,n3) (S(n22,n22). This completes the proof.

    Theorem 5.2. Let Tn be a tree on n8 vertices. If the diameter d(Tn)π47n81, then

    BH(Tn)>BH(K1,n1).

    Proof. Since 1cosx<x22, by Lemma 2.7, we have

    λ2(Tn)2(1cos(π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+(n22)1(22n)2+2n1n2)>n((d(Tn)+1)4π4+(n22)1(22n)2+(2n1)1n2)=n((d(Tn)+1)4π4+n2(n4)8(n1)2+(2n1)1n2)n(7n8+n2(n4)8(n1)2+(2n1)1n2)>n(n1)>n(n2+1n2)=BH(K1,n1)

    for n8. This completes the proof.

    The following conjecture is concretization of Problem 6.3 in [36].

    Conjecture 5.3. Let Tn be a tree on n5 vertices. Then

    BH(K1,n1)BH(Tn)BH(Pn),

    the left (right) equality holds if and only if Tn=K1,n1 (Tn=Pn).

    Theorem 5.4. Let G be a connected graph with n vertices and diameter d(G)=2. Then

    BH(G)BH(K1,n1)

    with equality if and only if G=K1,n1.

    Proof. It is well known that λnΔ+1 and λn1Δ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(n3+1Δ22+1(Δ+1)2)<n(n3+122+1(2+1)2)<n(n2+1n2)=BH(K1,n1).

    Thus Δ2=1, that is, G=K1,n1, then BH(G)=BH(K1,n1).

    Combining the above arguments, we have BH(G)BH(K1,n1) with equality if and only if G=K1,n1. This completes the proof.

    Theorem 5.5. Let Fs,t,n2s2t1 (s0,t0,n2s2t10) be a firefly graph with n7 vertices.

    (1) If s=t=0, then BH(F0,0,n1)=n22n+1n.

    (2) If s=0 and t=1, then BH(F0,1,n3)=n2+3n16+4n.

    (3) If s=0, t2 and n is odd, then

    n2+8n+25n32BH(F0,t,n2t1)7n2241n4+254n+12,

    the left (right) equality holds if and only if F0,t,n2t1=F0,2,n5 (F0,t,n2t1=F0,n12,0).

    If s=0, t2 and n is even, then

    n2+8n+25n32BH(F0,t,n2t1)7n2251n4+16n+4,

    the left (right) equality holds if and only if F0,t,n2t1=F0,2,n5 (F0,t,n2t1=F0,n22,1).

    (4) If s1, t=0 and n is odd, then

    5n2914n9+1nBH(F0,t,n2t1)n2269n+1n,

    the left (right) equality holds if and only if Fs,0,n2s1=F1,0,n3 (Fs,0,n2s1=Fn12,0,0).

    If s1, t=0 and n is even, then

    5n2910n9+1nBH(F0,t,n2t1)n2269n+1n,

    the left (right) equality holds if and only if Fs,0,n2s1=F1,0,n3 (Fs,0,n2s1=Fn22,0,1).

    (5) If s1, t1 and n is odd, then

    5n29+13n3+4n16BH(Fs,t,n2s2t1)7n22581n36+1214n+152,

    the left (right) equality holds if and only if Fs,t,n2s2t1=Fn32,1,0 (Fs,t,n2s2t1=F1,n32,0).

    If s1, t1 and n is even, then

    5n29+43n9+4n16BH(Fs,t,n2s2t1)7n22671n36+49n+11,

    the left (right) equality holds if and only if Fs,t,n2s2t1=Fn42,1,1 (Fs,t,n2s2t1=F1,n42,1).

    Proof. (1) If s=t=0, then F0,0,n1K1,n1. Thus BH(F0,0,n1)=n22n+1n.

    (2) If s=0 and t=1, by Lemma 2.10, we have

    ϕ(L(F0,1,n3))=ϕ(L(K1,n3))ϕ(L(P2))(x1)n3ϕ(L(P2))(x1)ϕ(L(K1,n3))=x2(x2)(xn+2)(x1)n4x(x2)(x1)n3x(xn+2)(x1)n3=x(x1)n4[x3(n+2)x2+(3n2)xn].

    By a similar reasoning as the proof of Theorem 5.1, we have

    BH(F0,1,n3)=n2+3n16+4n.

    (3) If s=0 and t2, then we have

    ϕ(L(F0,t,n2t1))=x(x1)n2t2(x23x+1)t1[x3(nt+3)x2+(3n3t+1)xn].

    By a similar reasoning as the proof of Theorem 5.1, we have

    BH(F0,t,n2t1)=n2+5tn11n+2t+(3n3t+1)2n6=n22n+9t2+(5n216n6)t+1n.

    If 2tn12 for odd n, we have

    n2+8n+25n32BH(F0,t,n2t1)7n2241n4+254n+12,

    the left (right) equality holds if and only if F0,t,n2t1=F0,2,n5 (F0,t,n2t1=F0,n12,0). If 2tn22 for even n, we have

    n2+8n+25n32BH(F0,t,n2t1)7n2251n4+16n+4,

    the left (right) equality holds if and only if F0,t,n2t1=F0,2,n5 (F0,t,n2t1=F0,n22,1).

    (4) If s1 and t=0, by Lemma 2.10, we have

    ϕ(L(Fs,0,n2s1))=x(xn)(x3)s(x1)ns2.

    Thus

    BH(Fs,0,n2s1)=n289sn2n+1n.

    If 1sn12 for odd n, we have

    5n2914n9+1nBH(F0,t,n2t1)n2269n+1n,

    the left (right) equality holds if and only if Fs,0,n2s1=F1,0,n3 (Fs,0,n2s1=Fn12,0,0). If 1sn22 for even n, we have

    5n2910n9+1nBH(F0,t,n2t1)n2269n+1n,

    the left (right) equality holds if and only if Fs,0,n2s1=F1,0,n3 (Fs,0,n2s1=Fn22,0,1).

    (5) If s1 and t1, by Lemma 2.10, we have

    ϕ(L(Fs,t,n2s2t1))=x(x3)s(x1)ns2t2(x23x+1)t1[x3(nt+3)x2+(3n3t+1)xn].

    By a similar reasoning as the proof of Theorem 5.1, we have

    BH(L(Fs,t,n2s2t1))=n289sn2n+9t2+(5n216n6)t+1n.

    If s=1 and t=n32 for odd n, we have

    BH(Fs,t,n2s2t1)max=7n22581n36+1214n+152,

    the equality holds if and only if Fs,t,n2s2t1=F1,n32,0.

    If s=1 and t=n42 for even n, we have

    BH(Fs,t,n2s2t1)max=7n22671n36+49n+11,

    the equality holds if and only if Fs,t,n2s2t1=F1,n42,1.

    If s=n32 and t=1 for odd n, we have

    BH(Fs,t,n2s2t1)min=5n29+13n3+4n16,

    the equality holds if and only if Fs,t,n2s2t1=Fn32,1,0.

    If s=n42 and t=1 for even n, we have

    BH(Fs,t,n2s2t1)min=5n29+43n9+4n16,

    the equality holds if and only if Fs,t,n2s2t1=Fn42,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+2i(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)=nni=21(nλn+2i(G))2.

    Proof. By Lemma 6.1, we have the proof.

    The union of two graphs G1 and G2 is the graph G1G2 with vertex set V1(G)V2(G) and edge set E(G1)E(G2). The join G1G2 is obtained from G1G2 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 G1G2 are n1+n2, λi(G1)+n2 (2in1) and λj(G2)+n1 (2jn1).

    Theorem 6.4. Let G be a connected graph with n vertices. Then

    BH(G1G2)=(n1+n2)(1(n1+n2)2+n1i=21(λi(G1)+n2)2+n2j=21(λj(G2)+n1)2).

    Proof. By Lemma 6.3, we have the proof.

    The Cartesian product of G1 and G2 is the graph G1G2, 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 vsvtE(G2) or vs=vt and uiujE(G1).

    Lemma 6.5. ([8,26]) Let G1 and G2 be graphs on n1 and n2 vertices, respectively. Then the Laplacian eigenvalues of G1G2 are all possible sums λi(G1)+λj(G2), 1in1 and 1jn2.

    Theorem 6.6. Let G1 and G2 be two connected graphs. Then

    BH(G1G2)=n1n2(n1i=21λ2i(G1)+n2j=21λ2j(G2)+n1i=2n2j=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 uiujE(G1) or ui=uj and vsvtE(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, 1in1 and 2jn2.

    Theorem 6.8. Let G1 and G2 be connected graphs on n1 and n2 vertices, respectively.

    BH(G1[G2])=n1n2(n1i=21n22λ2i(G1)+n2j=2n1i=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)vV(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)=12uV(G)vV(G)(d(u)+d(v))d2B(u,v).

    (2) The Gutman biharmonic index:

    GBI(G)=12uV(G)vV(G)(d(u)d(v))d2B(u,v).

    (3) The eccentric biharmonic distance sum:

    ξB(G)=12uV(G)vV(G)(ε2b(u)+ε2b(v))d2B(u,v).

    (4) The multiplicative eccentricity biharmonic distance:

    ξB(G)=12uV(G)vV(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
  • Reader Comments
  • © 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(2163) PDF downloads(77) Cited by(0)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog