# Computing some Laplacian Coefficients of Forests

Authors: Ali Ghalavand; Ali Reza Ashrafi
Journal: Journal of Applied Mathematics
 (2022)

---

## Abstract

LetG be a finite simple graph with Laplacian polynomial ψG,λ=∑k=0n−1n−kckλk. In an earlier paper, the coefficients cn−4 and cn−5 for forests with respect to some degree-based graph invariants were computed. The aim of this paper is to continue this work by giving an exact formula for the coefficient cn−6.


---

## Body

## 1. Definitions and Notations

A simple undirected graph is a pairG=V,E consisting of a set V=VG of vertices and a set E=EG of 2-element subsets of V. The elements of E are called edges, and the number of elements in V is called the order of G. The notations nG and mG denote the number of vertices and edges of G, respectively. There are two other graph notations worth mentioning now. The first one is degGv which is the number of edges in G with one end point v, and the second one is degGe which is defined as the degree of vertex e in the line graph of G. Obviously, degGe=degGu+degGv−2.We use the notationuvw to denote the path of length two such that vertices u and w have degree one, and the vertex v has degree two. In a similar way, we use the notation uvwx to denote a path of length three.A graphG is said to be connected if for arbitrary vertices x and y in V, and there exists a sequence x=x0,x1,⋯,xr=y of vertices such that xixi+1∈E, 0≤i≤r−1. The distance between two vertices u and v in a connected graph G, dGu,v, is defined as the length of a shortest path connecting these vertices and the sum of such numbers is called the Wiener index of G, denoted by WG [1]. The hyper-Wiener index is a generalization of the Wiener index. It was introduced for trees by Randić in 1993 [2] and for a general graph by Klein et al. [3]. This topological index is defined as WWG=1/2∑u,v∈VGdu,v+d2u,v.A subgraphH of a graph G is a graph with vertex set VH and edge set EH, such that VH⊆VG and EH⊆EG. We use the notation H≤G to denote that H is subgraph of G. If Z⊆V, and then the induced subgraph GZ is the graph with vertex set Z and the edge set uv∈Eu,v⊆Z, and if H≤G, then G−H is a subgraph of G, with vertex set VG/VH and edge set EG/uvu,v∩VH≠∅.The subdivision graphS is a graph constructed from G by inserting a new vertex on each edge of G. It is clear that nS=nG+mG and mS=2mG.SupposeG is a graph containing two edges e and f. If the edges e and f have a common vertex u, then we write u=e∩f. In the case that e and f do not have common vertex, we will say the edges e and f are independent. If M⊆EG and all pair of edges in M are independent, then the set M is called a matching for G. A k-matching is a matching of size k, 1≤k≤n/2, and the number of such matchings is denoted by mk. The matching polynomial of G and α is defined by αG,x=∑k=0n/2−1kmkxn−2k, where x≠0. By definition, αG,0=1, see [4] for more details.In 1972, Gutman and Trinajstic′ [5] introduced the first degree-based graph invariant applicable in chemistry. This invariant is the first Zagreb index and can defined by the formula M12G=∑v∈VdegGv2. The second Zagreb index M21G=∑uv∈EdegGudegGv was introduced by Gutman et al. [6] three years later in 1975. The complete history of these graph invariants together with the most important mathematical results about them are reported in [7–10].The forgotten index ofG is another variant of the Zagreb group indices defined as M13G=∑v∈VdegGv3=∑e=uv∈EdegGu2+degGv2 [11]. It can be see that M1αG=∑u∈VdegGuα, and ℝ∋α≠0,1 is the general form of the first Zagreb index. Zhang S. and Zhang H. [12] obtained the extremal values of the general Zagreb index in the class of all unicyclic graphs. Miličević et al. [13] reformulated the first and second Zagreb indices in terms of the edge-degrees instead of the vertex-degrees. These invariants were defined the first and second reformulated Zagreb indices defined as EM1G=∑e∩f≠∅degGe+degGf=∑e∈EdegGe2 and EM2G=∑e∩f≠∅degGedegGf, respectively.A0,1-matrix is a matrix whose entries consist only of the numbers 0 and 1. Suppose G is a graph with vertex set V=u1,⋯,un. The adjacency matrix of G is a 0,1-matrix AG=aij in which aij=1 if and only if uiuj∈E. It is easy to see that A is a real symmetric matrix of order n and so all of its eigenvalues are real. The matrices DG=dij and LG=DG−AG in which dii=degui and dij=0,i≠j, are called the diagonal and Laplacian matrices of G, respectively. It is well-known that all eigenvalues of LG are nonnegative real numbers with 0 as the smallest eigenvalue.The Laplacian polynomial of a graphG is one of the most important polynomial associated to a graph. If G is a graph, then the Laplacian polynomial of G is the characteristic polynomial of LG. The roots of this polynomial are called the Laplacian eigenvalues of G. Suppose ψG,x=detxIn−L=∑k=0n−1n−kckxk denotes the Laplacian polynomial of G. Since the coefficients of the Laplacian polynomial have graph theoretical meaning, some authors took into account the coefficients of this polynomial.Letf be a topological index and G be a graph. For simplifying our arguments, we usually write f as fG.Lemma 1.
SupposeG is a graph. The following statements hold:
(1)
(Merris [14] and Mohar [15]) c0G=0, c1G=nτG, cnG=1 and cn−1G=2m, where τG is the number of spanning trees of G;(2)
(Yan and Yeh [16]) c2G=WG, when G is a tree;(3)
(Gutman [17]) c3G=WWG, when G is a tree;(4)
(Oliveira et al. [18]) cn−2G=1/24m2−2m−M12 and cn−3G=1/3!4m22m−3−6M12m+6M12+2M13−12tG, where tG is the number of triangles in G.In [19–21], we proved the following formulas for the coefficients cn−4G and cn−5G, when G is a forest, respectively:
(1)cn−4G=14!4m4m3−12m2+51m−6M12m−33M12+4M13+3+3M1217M12−20+72M13−54M14−24M21−16∑u,v⊂VGdegGu2degGv2=14!4m4m3−12m2+3m−6M12m+15M12+4M13+3+3M12−22−24M13−6M14−24M21−12,(2)cn−5G=15!2m16m4−80m3+60m2−40M12m2+60m+180M12m+40M13m+15M122−120M12−140M13−30M14−120M21−20M123M12+M13+6+120M13+120M14+24M15+240M21+120α1,2.Supposeλ and ξ are two arbitrary real numbers. We now define three invariants which is useful in simplifying formulas in our results. These are
(3)αλ,ξG=∑uv∈EdegGuλdegGvξ+degGuξdegGvλ,βG=∑e~fdegGe∩fdegGe+degGf,M2λG=∑uv∈EdegGudegGvλ.Note that the second Zagreb index is just the case ofλ=1 in M2λ.LetG and H be graphs. Set SHG=XX≤GandX≅H. If f and g are two degree-based graph invariants, and then we define two new degree-based topological indices fg and Hf as fgG=fG×gG and HfG=∑X∈SHGfG−X.LetPn denote the path graph on n vertices. In a recent paper [22], Das et al. presented the following formula for the number of k-matchings, 1≤k≤n/2, in a graph G as
(4)mkG=1kP2mk−1G.They also proved the following two results:Lemma 2.
LetG be a graph with n vertices and m edges. Then
(1)
P2mG=m2+m−M12.(2)
P2m2G=m3+M13−2mM12+2M21+2m2−2M12+m.(3)
P2m3G=m4−3m2M12+3mM13+6mM21−M14−3α1,2+3m3−6mM12+3M13+6M21+3m2−3M12+m.(4)
P2m4G=M15+4α1,3−4mM14+6M22−12mα1,2+6m2M13+12m2M21−4m3M12−4M14−12α1,2+12mM13+24mM21−12m2M12+6M13+12M21−12mM12−4M12+m5+4m4+6m3+4m2+m,(5)
P2m5G=m6+5m5+10−5M12m4+10+10M13+20M21−20M12m3+5+60M21−10M14−30α1,2+30M13−30M12m2+30M22−60α1,2+5M15+20α1,3+30M13−20M12+60M21−20M14+1m+20α1,3−5α1,4−10α2,3+10M13−5M12+20M21−10M14+5M15−M16+30M22−30α1,2.Lemma 3.
LetG be a graph with n vertices, m edges and girth ≥5. Then
(1)
P2M12G=m+3M12−M13−4M21−2m.(2)
P2M13G=m+3M13−M14−3α1,2+6M21−4M12+2m.(3)
P2M14G=m+4M14−M15+5M12−2m−4α1,3+6α1,2−6M13−8M21.(4)
P2M21G=m−9M21−2EM2−5M13+11M12+M14+α1,2−8m.(5)
P2mM12G=M12−2m2+4M12−M13−4M21−18m−6M13+α1,2−2β+17M12−6M21+8EM1+4EM2−M12+M14.The following theorem is crucial in our main result [21].Theorem 4.
LetG be a graph with m edges. Then
(1)
m5SG=1/15m24m3−20m2+15m+15+1/12m8M13m−8M12m2+3M122+36M12m−28M13−24M12−6M14−24M21+α1,2−1/6M123M12+M13+6+2M21+1/5M15+M14+M13.(2)
M12SG=M12+4m,M13SG=M13+8m,M14SG=M14+16m,M15SG=M15+32m,α1,2SG=4M12+2M13,α1,3SG=8M12+2M14,βSG=2M12+M14−M13,M21SG=2M12,M22SG=4M13,EM1SG=M13,EM2SG=M21+1/2M14−1/2M13.(3)
P2M122SG=2m−10M122+16m2−2M13−40mM12+32m3−8mM13+13M13+6M14+M15+24M21+4α1,2.(4)
P2m2M12SG=32m4+8M12−32m3−4M13+44M12−8m2+20M13−4M122+30M12+4M14+16M21m+M13M12+2M122−7M13−5M12−5M14−M15−8M21−2α1,2.(5)
P2mM13SG=32m3+4M13−24m2−8M13+16M12+2M14m+4m−M12−10M13+6M12+M14+M15−6M21+3α1,2.(6)
P2mM21SG=8M12+8m2−4M13+10M12+4M21+4m−2M122+2M13+M12+2M14+8M21+α1,2.(7)
P2EM2SG=1/2m4M21−2M13+2M14+4+11/2M13−2α1,2−7/2M12−3/2M14−1/2M15.


## 2. Laplacian Coefficients and Degree-Based Invariants

The aim of this section is to present an exact formula for the coefficientcn−6 of the Laplacian polynomial in terms of some degree-based graphs invariants.Lemma 5.
LetG be a graph with n vertices and m edges. Then, M16SG=M16+64m,α1,4SG=2M15+16M12,α2,3SG=4M14+8M13.Proof.
Apply definition ofSG, to prove that M16SG=M16+64m, α1,4SG=∑v∈V∑uv∈E2degGv4+16degGv=∑v∈V2degGv5+16degGv2=2M15+16M12 and α2,3SG=∑v∈V∑uv∈E4degGv3+8degGv2=∑v∈V4degGv4+8degGv3=4M14+8M13.The next lemma is a direct consequence of Lemmas2 and 5 and Theorem 4 (2).Lemma 6.
LetG be a graph with n vertices and m edges. Then,
(1)
P2mSG=4m2−2m−M12.(2)
P2m2SG=M13+2M12−2m2M12−4m2+4m−1.)(3)
P2m3SG=16m4−24m3−12M12−12m2+6M13+12M12−2m−3M13−3M12−M14.(4)
P2m4SG=32m5−64m4−32M12−48m3+24M13+48M12−16m2−24M13+24M12+8M14−2m+6M13+4M12+4M14+M15.(5)
P2m5SG=64m6−160m5−80M12−160m4+80M13+160M12−80m3−120M13+120M12+40M14−20m2+60M13+40M12+40M14+10M15−2m−10M13−5M12−10M14−5M15−M16.It is easy to see that girthG≥6. Therefore, Lemma 3 and Theorem 4 (2) imply the following lemma:Lemma 7.
LetG be a graph on n vertices and m edges. Then,
(1)
P2M12SG=2m−5M12+8m2−M13.(2)
P2M13SG=16m2+2M13−4m−3M13−4M12−M14.(3)
P2M14SG=2m−4M14+32m2+6M13−19M12−M15.(4)
P2M21SG=4mM12−2M13−3M12−2M21+4m.(5)
P2mM12SG=16m3+4M12−8m2−2M13+16M12m−M122+4M13+5M12+4M21+M14.Lemma 8.
LetG be a graph with n vertices and m edges. Then, P2M15SG=2mM15+64m2−M16−4m−5M15+10M14−10M13−26M12.Proof.
Apply definition ofP2M15SG to show that P2M15SG=2mM15SG−∑v∈V∑uvdegGv5+5degGv4−10degGv3+10degGv2+26degGv+2=2mM15SG−∑v∈VdegGv6+5degGv5−10degGv4+10degGv3+26degGv2+2degGv. Now the proof follows from Theorem 4 (2) and simple calculations.Lemma 9.
LetG be a graph with n vertices and m edges. Then, P2m3M12SG=64m5+16M12−96m4+−8M13−112M12+48m3+−12M122+72M13+120M12+12M14+48M21−8m2+12M122+6M13−44M12−54M13−48M21−34M14−6M15−12α1,2m−3M122+−3M13−M14+5M12+10M13+12M21+12M14+6M15+M16+6α1,2+2α1,3.Proof.
By definition ofSG, P2m3M12SG=∑v∈V∑uv∈E2m−degGv−13M12SG−degGv2−3degGv−2degGu. Suppose X=16m4M12SG+−8M13−24M12−24M12SGm3+−12M12+12M12SG+36M12+12M14m2+6M13+12M12−2M12SG−42M13−18M12−6M15−30M14m+−3M13−3M12−M14M12SG+10M13+3M12+12M14+6M15+M16. Then, P2m3M12SG=X+∑v∈V∑uv∈E−16m3degGu+2degGu+24m2degGudegGv+48m2degGv2−12mdegGudegGv2+2degGudegGv3+24mdegGudegGv+6degGudegGv2−12mdegGu+6degGudegGv. We now replace ∑v∈V∑uv∈E by ∑uv∈E to show that P2m3M12SG=X−16m3M12+48M13+24M12+48M21m2+−12M12−48M21−12α1,2m+2M12+12M21+6α1,2+2α1,3. The proof now follows from Theorem 4 (2).Lemma 10.
LetG be a graph with n vertices and m edges. Then, P2m2M13SG=64m4+8M13−80m3+−20M13−48M12−4M14+32m2+−4M12+50M13+40M12−24M21+4M14+4M15+12α1,2−4m+M132+2M12−19M13−8M12+12M21−8M14−2M15−M16−6M22−3α1,2.Proof.
Apply definition ofSG to show that P2m2M13SG=∑v∈V∑uv∈E2m−degGv−12M13SG−degGv3−3degGu2+3degGu−7degGv−2. Now a similar argument as Lemma 9 completes the proof.Lemma 11.
LetG be a graph with n vertices and m edges. Then, P2mM14SG=4M14+64mm2−32m2+12M13−54M12−10M14−2M15m+4−M12M14+9M13+19M12+8M21+M15+M16−6α1,2+4α1,3.Proof.
Apply definitions ofSG and P2mM14 to write the form P2mM14SG=∑v∈V∑uv∈E2m−degGv−1M14SG−degGv4−4degGu3+6degGu2−4degGu−15degGv. Now a similar argument as Lemma 9 gives the proof.Lemma 12.
LetG be a graph with n vertices and m edges. Then, P2α1,2SG=24M12+2M13m−9M13+M12−2M14−6M21−α1,2+4m.Proof.
By definitions ofSG and α1,2, we can write
(5)P2α1,2SG=2mα1,2SG−∑v∈V2degGv2+4degGvdegGv2+degGv+2degGv2+4degGvdegGv2−degGv−2degGv−12+4degGv−1degGv2−degGv−∑v∈V∑uv∈E2degGv2+4degGv−degGv2+degGvdegGu−1.
Now by simple calculations, we obtain(6)P2α1,2SG=2mα1,2SG−10M13−2M12−2M14+4m−∑uv∈EdegGudegGv2+degGu2degGv+6degGudegGv−degGu2−degGv2−3degGu−3degGv=2mα1,2SG−10M13−2M12−2M14+4m−α1,2−6M21+M13+3M12,and Theorem 4 (2) gives the result.Lemma 13.
LetG be a graph with n vertices and m edges. Then, P2mM122SG=64m4+32M12−32m3+4M122−16M13−112M12m2+−30M122+−4M13+40M12+58M13+80M21+20M14+2M15+8α1,2m−M123+10M122+8M13+8M21+2M14M12−13M13−24M21−15M14−7M15−M16−20α1,2−4α1,3.Proof.
By definition ofSG,P2mM122SG=∑v∈V∑uv∈E2m−degGv−1M12SG−degGv2−3degGv−2degGu2. Now the proof follows from a similar argument as Lemma 9.Lemma 14.
LetG be a graph with n vertices and m edges. Then, P2M12M13SG=64m3+8M13+16M12−16m2+2M13−60M12−20M13−4M14m−4M122+−8M13−M14+10M12−M132+17M13+2α1,3+10M21+13M14+3M15+M16+6M22+6α1,2.Proof.
By definition ofSG,P2M12M13SG=∑v∈V∑uv∈EM12SG−degGv2−3degGv−2degGuM13SG−degGv3−3degGu2+3degGu−7degGv−2. Now the proof can be completed in a similar way as Lemma 9.Define nine graph invariants as(7)Θ1G=∑uvw∈SP3GdegGudegGvdegGw,Θ2G=∑uvw∈SP3GdegGudegGw,Θ3G=∑uvwx∈SP4GdegGudegGx,Θ4G=∑uvw∈SP3GdegGu2degGw+degGudegGw2,Θ5G=∑uvw∈SP3GdegGv2degGu+degGw,Θ6G=∑uvwx∈SP4GdegGudegGv+degGwdegGx,Θ2+G=∑uvw∈SP3GdegGu+degGw,Θ3+G=∑uvwx∈SP4GdegGu+degGx,Θ3+,2G=∑uvwx∈SP4GdegGu2+degGx2.Lemma 15.
LetG be a graph with n vertices and m edges. Then, P2M122G=m+6M122+−2M13−4m−8M1/2−12M12+M13+M15+2M22−6α1,2+4α1,3+4m+26M21−2M14+8Θ1−24Θ2+8Θ3+4Θ4.Proof.
By definition ofM12 and some tedious calculations, one can see that
(8)P2M122G=∑uv∈EM12−degGu2−degGv2−∑xu∈EG−uv2degGx−1−∑yv∈EG−uv2degGy−12=m+2M122+−2M13−4m−4M12+5M13−2M14+M15+2M21+2M22−2α1,2+4m+∑uv∈E4degGu2∑xu∈EG−uvdegGx+4degGu2∑yv∈EG−uvdegGy+4degGv2∑xu∈EG−uvdegGx+4degGv2∑yv∈EG−uvdegGy−4M12−8∑xu∈EG−uvdegGx−4M12−8∑yv∈EG−uvdegGy−4degGu∑xu∈EG−uvdegGx−4degGu∑yv∈EG−uvdegGy−4degGv∑xu∈EG−uvdegGx−4degGv∑yv∈EG−uvdegGy+∑xu∈EG−uv2degGx2+∑yv∈EG−uv2degGy2+2∑xu∈EG−uv2degGx∑vy∈EG−uv2degGy.
Therefore,P2M122G=m+6M122+−2M13−4m−8M21−12M12+M13+M15+2M22−6α1,2+4α1,3+4m+26M21−2M14+8Θ1−24Θ2+8Θ3+4Θ4, proving the lemma.Lemma 16.
LetG be a graph with n vertices and m edges. Then, P2mM13G=M13+2m2+4M13−3α1,2−4M12+6M21−M14+2m+−M12+4M13−9α1,2+α1,3−6M12+14M21−6Θ2+3Θ4−M14+M15+6M22.Proof.
Chooseuv∈E and set Auv=∑xu∈EG−uv3degGx2−3degGx+1 and Buv=∑yv∈EG−uv3degGy2−3degGy+1. Apply definition of P2mM13 to prove that P2mM13G=∑uv∈Em−degGu−degGv+1M13−degGu3−degGv3−Auv−Buv. Therefore
(9)P2mM13G=m2M13−M12M13+mM13−mM12−mM14+2m2+M13−3M12−M14+M15+2M21+α1,3+2m−3∑uv∈Em−degGu−degGv+1∑xu∈EG−uvdegGx2−degGx+∑yv∈EG−uvdegGy2−degGy.
Now, a similar argument as Lemma15 gives our result.Lemma 17.
LetG be a graph with n vertices and m edges. Then, P2m2M12G=M12−2m3+−M13+5M12−4M21−4m2+−2M122−4M13+11M12+2M14−20M21+6α1,2+8Θ2−2m−2M122+M13+2M21+7M12−5M13+11α1,2−4α1,3−2Θ4−20M21−8Θ1+8Θ2+3M14−M15−2M22.Proof.
Apply definition ofP2m2M12 and some tedious calculations to show that
(10)P2m2M12G=M12−2m3+−M13+3M12−4m2+−2M122−4M13+7M12+2M14−4M21+2α1,2−2m−2M122+M13+2M21+5M12−5M13−8M21+3M14−M15−2M22+5α1,2−2α1,3−2∑uv∈Em−degGu−degGv+12∑xu∈EG−uvdegGx+∑yv∈EG−uvdegGy.
Now, a similar argument as Lemma15 gives the proof.Lemma 18.
LetG be a graph with n vertices and m edges. Then, EM2G=α1,2−6M21+1/2M14−5/2M13+6M12−4m+Θ2.Proof.
By definition ofEM2,EM2G=∑uvw∈SP3GdegGu+degGv−2degGv+degGw−2=α1,2−6M21+1/2M14−5/2M13+6M12−4m+Θ2.Lemma 19.
LetG be a graph with n vertices and m edges. Then, P2Θ2G=m+2Θ2−Θ1−Θ4−2Θ3+Θ3+.Proof.
By definition ofP2Θ2,
(11)P2Θ2G=mΘ2−∑uvw∈SP3GdegGudegGwdegGu+degGv+degGw−2−∑xyab∈SP4G2degGxdegGb−degGx−degGb=m+2Θ2−Θ1−Θ4−2Θ3+Θ3+,as desired.By a similar arguments as Lemma15, we can prove the following two lemmas:Lemma 20.
LetG be a graph with n vertices and m edges. Then, P2mM21G=m2M21+2M21−2Θ2−α1,2+Θ2+m−M12−1M21+Θ2++2Θ1−4Θ2+2Θ3+Θ4+Θ5.Lemma 21.
LetG be a graph with n vertices and m edges. Then, P2α1,2G=m+1α1,2−2M22−α1,3+Θ3+−Θ3+,2−2Θ6.For the sake of completeness, we mention here two results which are useful in our next calculations.Lemma 22 (see [19]).
LetG be a graph. Then, βG=α+M14−3M13+2M12−2M21.Theorem 23 (see [4]).
LetG be a graph with m edges and girth ≥5. Then, m5G=1/5!mm4+10m3+43m2+54m−328+30M122−12α1,2m−7−20α1,3−2M122m3+30m2+61m−225+12β+2M216m2+66m−239+M136m2+24m−149+2M14m+10+6M22−EM2−5M15+3P2M122+8P2mM13−6P2m2M12−P2EM2+P2mM21.Now, Lemmas2 (1), 3, 15, 16, 17, 18, 19, 20, 21,and 22 and Theorem 23 give the following theorem:Theorem 24.
LetG be a graph with m edges and girth ≥5. Then, m5G=1/5!m5+10m4−10M12−55m3+60M21−90M12+20M13+190m2+15M122+140M13−376M12−30M14+492M21−120α1,2−120Θ2+24Θ2++336m+60M122−60M21+20M13+768M12−120M14+24M15+120M22−504α1,2+96α1,3+24Θ2+−48Θ3++96Θ4+24Θ3+,2+336M13+1440M21+132Θ1−600Θ2+120Θ3+24Θ5+48Θ6.Lemma 25.
LetG be a graph with n vertices and m edges. Then, Θ1SG=2M21+M13−M12, Θ2SG=M21+2M12−4m, Θ2+SG=3M12−4m, Θ3SG=4M21−2M12, Θ3+SG=2M21+M12−4m, Θ3+,2SG=α1,2+4M12−M13−8m, Θ4SG=α1,2+8M12−16m, Θ5SG=4M12+2M14−2M13, andΘ6SG=4M21+2M13−4M12.Proof.
The proof is straightforward and so it is omitted.Lemma 26.
LetG be a graph with n vertices and m edges. Then, P2Θ2SG=4M12+2M21+4m−8m2−2M13+3M12−6M21−α1,2.Proof.
Lemmas19, 25, and 6 (1) give our result.Lemma 27.
LetG be a graph with n vertices and m edges. Then,
(1)
P2Θ1SG=4M13−4M12+4M21−8m−2M13+10M12−2M14−4α1,2,(2)
P2Θ2+SG=6M12+8m−8m2−3M13−M12−4M21,(3)
P2Θ3SG=8M21−4M12−4m+2M13+6M12−4M21−4α1,2−2Θ2+Θ2+,(4)
P2Θ3+SG=2m2M21+M12−4m−M13+6M12−6M21−2α1,2−Θ2+,(5)
P2Θ3+,2SG=8M12−2M13+2α1,2+4m−16m2−M13+3M12−2M21+M14−2M22−2α1,2−α1,3−3Θ2+,(6)
P2Θ4SG=16M12+2α1,2+12m−32m2−7M13+11M12−14M21−2M22−3α1,2−α1,3,(7)
P2Θ5SG=4M14−4M13+8M12+16m+13M13−18M12−8M21−5M14−2M15+α1,2−α1,3,(8)
P2Θ6SG=4M13−8M12+8M21−12m+M13+13M12+2M21−2M14−7α1,2,(9)
P2mΘ2SG=8M12+4M21+16m2−16m3+4M12−4M13−10M21−2α1,2−2Θ2+−4m−2M122−M21+4M12−2M13+8M21+2Θ2+2M14+3α1,2+α1,3+Θ2+,(10)
P2mΘ2+SG=12M12+24m2−16m3−6M13+4M12+8M21+8m−3M122−3M12+12M21+3M14+2α1,2.Proof.
The proof has tedious calculations similar to Lemma15.Lemma 28.
LetG be a graph with n vertices and m edges. Then,
(1)
P2α1,3SG=16M12+4M14+20m+4M13−17M12−14M21−7M14−2M15−α1,3.(2)
P2mα1,2SG=8M13+16M12+8m2−22M13+6M12+12M21+4M14+2α1,2+4m−4M122−2M13+3M12+9M13+4M21+6M14+2M15+2M22+9α1,2.(3)
P2M12M21SG=4m−13M122+16m2−4M13−2M21−8m−10M12+16m2−8M13+8M21m+6M13+18M21+4Θ2+6M14+2M15+10α1,2+α1,3.(4)
P2m2M21SG=16M12+16m3−8M13+28M12+8M21+16m2+8M13−8M122+8M12+8M14+32M21+4α1,2+4m+4M122+2M13+1M12−14M21−4M14−2M15−5α1,2−α1,3.(5)
P2M22SG=8m−9M13−8m+12M12−4M14−3α1,2.Proof.
By definitions ofSG, we have
(12)P2α1,3SG=2mα1,3SG−∑v∈V∑uv∈E2degGv3+8degGvdegGv+2degGu3+8degGu+2degGu3+8degGudegGu−1−2degGu−13+8degGu−1degGu−1+∑xv∈EG−uvdegGx3+7degGx=16M12+4M14+20m+4M13−17M12−14M21−7M14−2M15−α1,3,P2mα1,2SG=∑v∈V∑uv∈E2m−degGv−1α1,2SG−2degGv2+4degGvdegGv−2degGu2−4degGu−2degGu2+4degGudegGu−1+2degGu−12−4degGu−1degGu−1−∑xv∈EG−uvdegGx2+3degGx=8M13+16M12+8m2−22M13+6M12+12M21+4M14+2α1,2+4m−4M122−2M13+3M12+9M13+4M21+6M14+2M15+2M22+9α1,2,P2M12M21SG=∑v∈V∑uv∈EM12SG−degGv2−3degGv−2degGuM21SG−2degGv2−2degGu−2degGudegGu−1+2degGu−12−∑xv∈EG−uvdegGx=4m−13M122+16m2−4M13−2M21−8m−10M12+16m2−8M13+8M21m+6M13+18M21+4Θ2+6M14+2M15+10α1,2+α1,3,P2m2M21SG=∑v∈V∑uv∈E2m−degGv−12M21SG−2degGv2−2degGu−2degGudegGu−1+2degGu−12−∑xv∈EG−uvdegGx=16M12+16m3−8M13+28M12+8M21+16m2+8M13−8M122+8M12+8M14+32M21+4α1,2+4m+4M122+2M13+1M12−14M21−4M14−2M15−5α1,2−α1,3,P2M22SG=∑v∈V∑uv∈EM21SG−4degGv3−4degGu2−4degGu2degGu−1+4degGu−13−∑xv∈EG−uv3degGx2=8m−9M13−8m+12M12−4M14−3α1,2,proving the lemma.Theorem 29.
LetG be a graph with m edges. Then, m6SG=1/6!64m6−480m5+720m4+600m3−360m2−480m−720M15−2160α1,2−720α1,3+540M122−2340m2M12+2160mM13−1080M14+720M21−240M12M13m−120M16−720M22+600M12M13+1680M12m3−810M122m−1920M13m2+1620M14m+3600M21m−720Θ2−1260mM12+720M12+480M13−240m4M12+320m3M13+360M12M21+90M12M14+180M122m2−360M14m2−1440M21m2+288M15m+1440α1,2m+40M132−15M123.Proof.
The proof follows from Theorems24 and 4, Equation (4), and Lemmas 6, 7, 8, 9, 10, 11, 12, 13, 14, 26, 27, and 28.We mention here a useful result of Zhou and Gutman [23].Theorem 30.
LetG be an n-vertex forest. Then, cn−kG=mkSG, for0≤k≤n.We are now ready to prove the main result of this section.Theorem 31.
LetG be a forest with m edges. Then, cn−6G=1/6!64m6−480m5+720m4+600m3−360m2−480m−720M15−2160α1,2−720α1,3+540M122−2340m2M12+2160mM13−1080M14+720M21−240M12M13m−120M16−720M22+600M12M13+1680M12m3−810M122m−1920M13m2+1620M14m+3600M21m−720Θ2−1260mM12+720M12+480M13−240m4M12+320m3M13+360M12M21+90M12M14+180M122m2−360M14m2−1440M21m2+288M15m+1440α1,2m+40M132−15M123.Proof.
The proof follows from Theorems29 and 30.IfT is an n-vertex tree, then m=n−1. Therefore by previous theorem we have the following corollary:Corollary 32.
LetT be a tree on n vertices. Then, cn−6T=1/6!8n−18n5−100n4+410n3−635n2+355n−98−240M12M13n+1440α1,2n+288M15n+9420M12n−1170M122n+2340M14n+6480M21n+6960M13n−1440M21n2+180M122n2−360M14n2+320M13n3−2880M13n2−240M12n4+2640M12n3−8820M12n2+360M12M21+90M12M14+840M12M13−15M123+40M132+1530M122−720Θ2−120M16−720M22−3920M13−3060M14−4320M21−2280M12−720α1,2−1008M15−3600α1,2.


## 3. Applications

This section aims is to apply our results in Section3 for computing the Laplacian coefficients cn−k, k=2,3,4,5,6, when G is a certain tree. Let G be a graph. The number of edges connecting vertices of degree i and j in a graph G is denoted by mi,j. Let P3i,j=uvw∈SP3GdegGu,degGw=i,j. As [21], we first assume that Tk,t be a rooted tree with degree sequence k,k,⋯,k,1,1,⋯,1, and t is the distance between the center and any pendant vertex, as shown in Figure 1. By definition of Tk,t, we have nTk,t=kk−1t−2/k−2, m1,kTk,t=kk−1t−1, mk,kTk,t=nTk,t−1−m1,kTk,t, P31,k=m1,kTk,t, P31,1=kk−1t−2k−12, and P3k,k=1/2M1Tk,t−nTk,t+1−P31,1−P31,k. Therefore by Lemma 1, Equations (1) and (2), Corollary 32, and the others simple calculations, we have
(13)cn−1T3,t=6×2t−6,cn−2T3,t=18×22t−9322t+30,cn−3T3,t=36×23t−171×22t+272×2t−144,cn−4T3,t=54×24t−405×23t+9177822t−579942t+687,cn−5T3,t=324525t−702×24t+12267423t−26967422t+74427102t−3294,cn−6T3,t=324526t−4779525t+23697424t−3157111623t+14882934022t−376247102t+15932,cn−1T4,t=4×3t−4,cn−2T4,t=8×32t−24×3t+18,cn−3T4,t=32333t−64×32t+39233t−88,cn−4T4,t=32334t−320333t+1232332t−213233t+457,cn−5T4,t=1281535t−128×34t+2368333t−2480×32t+1964453t−2484,cn−6T4,t=2564536t−17921535t+9664934t−15776333t+6618644532t−11075653t+13990.Figure 1
The rooted treeT3,3.For example, see Tables1 and 2.Table 1
The Laplacian coefficientscn−xT3,t, where x,t∈2,3,4,5,6.
xt23456213281038941697470782351295201078881013104875403241146763292151219444810158044078715152444292632892762153204942658577653506611961926456401303300431095065723521109479132Table 2
The Laplacian coefficientscn−xT4,t, where x,t∈2,3,4,5,6.
xt234562450520250562466578423405033680166736525929614930753640985681604195493849829405115261356858940852971474597789571496682516802464744183267950683118721721091168665352618639496705733012336784030661073738466435154829575812820551386



---

*Source: 8199547-2022-10-22.xml*