# The Characterizing Properties of (Signless) Laplacian Permanental Polynomials of Almost Complete Graphs

Authors: Tingzeng Wu; Tian Zhou
Journal: Journal of Mathematics
 (2021)

---

## Abstract

LetG be a graph with n vertices, and let LG and QG denote the Laplacian matrix and signless Laplacian matrix, respectively. The Laplacian (respectively, signless Laplacian) permanental polynomial of G is defined as the permanent of the characteristic matrix of LG (respectively, QG). In this paper, we show that almost complete graphs are determined by their (signless) Laplacian permanental polynomials.


---

## Body

## 1. Introduction

We useG to denote a simple graph with vertex set VG=v1,v2,…,vn and edge set EG=e1,e2,…,em. The degree of a vertex v∈VG is denoted by dv. The degree matrix of G, denoted by DG, is the diagonal matrix whose i,ith entry is dvi. For a subgraph H of G, let G−EH denote the subgraph obtained from G by deleting the edges of H. Let ciG and piG denote, respectively, the numbers of i-cycles and i-vertex paths in G. Let c3Gv denote the number of triangles containing the vertex v of G. Let G∪H be the union of two graphs G and H which have no common vertices. For any positive integer l, let lG be the union of l disjoint copies of graph G. For convenience, the complete graph, path, cycle, and star on n vertices are denoted by Kn, Pn, Cn, and K1,n−1, respectively.Thepermanent of n×n matrix X=xiji,j=1,2,…,n is defined as(1)perX=∑σ∏i=1nxiσi,where the sum is taken over all permutations σ of 1,2,…,n. Valiant [1] has shown that computing the permanent is #P-complete even when restricted to (0, 1)-matrices.LetM be an n×n matrix. The permanental polynomial of M, denoted by πM,x, is defined to be the permanent of the characteristic matrix of M, i.e.,(2)πM=πM,x=perxI−M,where I is the identity matrix of size n.LetAG denote the adjacency matrix of G. The Laplacian matrix LG and signless Laplacian matrix QG of G are defined by LG=DG−AG and QG=DG+AG, respectively. We call πLG,x (resp, πQG,x) the Laplacian (resp, signless Laplacian) permanental polynomial of G. The Laplacian permanental polynomial of a graph was first considered by Merris et al. [2], and the signless Laplacian permanental polynomial was first studied by Faria [3]. For more studies on (signless) Laplacian permanental polynomials, see [4–14], among others.Two graphsG and H are called Laplacian copermanental if πLG,x=πLH,x. Analogously, signless Laplacian copermanental could be defined. A graph G is said to be determined by its Laplacian (resp, signless Laplacian) permanental polynomial if any graph Laplacian (resp, signless Laplacian) copermanental with G is isomorphic to G.It is interesting to characterize which graph is determined by graph polynomials [15–18]. Merris et al. [2] first discussed the problem: which graph is determined by its Laplacian permanental polynomial? Answer to the problem is very hard. Up to now, only a few results are known about the problem. Merris et al. computed the Laplacian permanental polynomials of all connected graphs on 6 vertices, and they found that there exist no nonisomorphic Laplacian copermanental graphs of such graphs. Based on the result, they stated that they do not know of a pair of nonisomorphic Laplacian copermanental graphs. Recently, Liu [19] showed that complete graph Kn and star Sn are determined by their (signless) Laplacian permanental polynomials.LetGn denote the set of graphs each of which is obtained from Kn, by removing five or fewer edges. Cámara and Haemers [20] showed that all graphs in Gn are determined by their characteristic polynomials of adjacency matrices of these graphs. The authors [21] proved that all graphs in Gn are determined by their Aα-spectra. In this paper, our interest is to discuss which graph in Gn is detertmined by its (signless) Laplacian permanental polynomial. And, we prove the following result.Theorem 1.
All graphs inGn are determined by their (signless) Laplacian permanental polynomial.The rest of this paper is organized as follows. In Section2, we present some characterizing properties of the (signless) Laplacian permanental polynomial and give some structural properties of graphs in Gn. In Section 3, we give the Proof of Theorem 1.


## 2. Preliminaries

LetGn denote the set of graphs each of which is obtained from Kn by removing five or fewer edges. For n≥10, there exist exactly 45 nonisomorphic graphs each of which is obtained from Kn by removing five or fewer edges [21, 22]. These graphs are labeled by Gij, 1≤i≤5,0≤j≤25, and illustrated in Figure 1. For some properties of graphs in Gn, see [21, 22], among others.Figure 1
The graphs obtained fromKn by deleting five or fewer edges drawn as lines in a disk.Lemma 1 (see [22]).
LetH⊆Kn be a graph with l edges and let G=Kn−EH. Then,(3)c3G=n3−ln−2+∑v∈VHdv2−c3H.In [22], the first author calculated the number of triangles of some G∈Gn, see Table 1.Table 1
The numbers of triangles of some graphs inGn.
Graphc3GG30n3−3n+9G32,G33n3−3n+8G41,G47n3−4n+11G44,G46,G410n3−4n+12G50,G51,G514n3−5n+12G52n3−5n+11G54n3−5n+20G53,G57,G518,G519,G522n3−5n+14G31n3−3n+7G40n3−4n+14G43n3−4n+9G42,G45,G48n3−4n+10G59,G524n3−5n+17G55,G512,G520,G523n3−5n+15G58,G511,G513,G517n3−5n+13G56,G510,G515,G516,G525n3−5n+16Lemma 2 (see [22]).
LetH⊆Kn be a graph with l edges and let G=Kn−EH. Then,(4)c4G=3n4−2ln−22+2l2+n−5∑v∈VHdv2−p4H+c4H.
In [22], the first author calculated the number of quadrangles of some G∈Gn, see Table 2.Table 2
The numbers of quadrangles of some graphs inGn.
Graphc4GG323n4−3n2+18n−27G423n4−4n2+22n−22G503n4−5n2+27n−21G533n4−5n2+29n−32G553n4−5n2+30n−38G5113n4−5n2+28n−26G58,G5143n4−5n2+28n−25G512, G5253n4−5n2+31n−44G5203n4−5n2+30n−40G41,G453n4−4n2+23n−27G483n4−4n2+22n−23G513n4−5n2+27n−20G573n4−5n2+29n−30G5233n4−5n2+30n−39G5173n4−5n2+28n−27G519, G5223n4−5n2+29n−33G5183n4−5n2+30n−37Lemma 3 (see [21]).
Letc3Gv denote the number of triangles containing the vertex v of G. Using the principle of inclusion-exclusion, we can obtain the following result. Let H⊆Kn be a graph with k edges and let G=Kn−EH. Let v∈VG and let v be an endpoint of l edges in EH. Then,(5)c3Gv=n−12−k−l−ln−1−l−l2+c3G¯vi+P3.Lemma 4 (see [19]).
LetG be a graph with n vertices and m edges, and let d1,d2,…,dn be the degree sequence of G. Suppose that πLG,x=∑ipiGxn−i. Then,(i)
p0G=1(ii)
p1G=−2m(iii)
p2G=2m2+m−1/2∑idi2(iv)
p3G=−1/2∑idi3+m+1∑idi2−4/3m3−2m2+2c3G(v)
p4G=−1/4∑idi4+2/3m+1∑idi3−1/22m2+5m+1∑idi2+1/8∑idi22+∑vivj∈EGdidj + 2∑idic3Gvi+2c4G−4mc3G+2/3m4+2m3+1/2m2+1/2mLemma 5 (see [19]).
LetG be a graph with n vertices and m edges, and let d1,d2,…,dn be the degree sequence of G. Suppose that πQG,x=∑iqiGxn−i. Then,(i)
q0G=1(ii)
q1G=−2m(iii)
q2G=2m2+m−1/2∑idi2(iv)
q3G=−1/3∑idi3+m+1∑idi2−4/3m3−2m2−2c3G(v)
q4G=−1/4∑idi4+2/3m+1∑idi3−1/22m2+5m+1∑idi2+1/8∑idi22 + ∑vivj∈EGdidj−2∑idic3Gvi+2c4G+4mc3G+2/3m4+2m3+1/2m2+1/2m
By Lemmas4 and 5, we have the following.Corollary 1.
LetG be a graph with n vertices and m edges, and let d1,d2,…,dn be the degree sequence of G. Suppose that πLG,x=∑ipiGxn−i and πQG,x=∑iqiGxn−i. Then,(i)
p3G−q3G=4c3G(ii)
p4G−q4G=4∑idic3Gvi−8mc3G
For convenience, we calculate the value∑idic3Gvi of some graphs in Gn, see Table 3.Table 3
The value of∑idic3Gvi of some graphs in Gn.
Graph∑idic3GviG301/2n4−2n3−19/2n2+56n−66G411/2n4−2n3−27/2n2+70n−66G421/2n4−2n3−27/2n2+65n−50G501/2n4−2n3−35/2n2+79n−48G531/2n4−2n3−35/2n2+89n−79G581/2n4−2n3−35/2n2+84n−62G5191/2n4−2n3−35/2n2+89n−80G5111/2n4−2n3−35/2n2+84n−61G551/2n4−2n3−35/2n2+94n−94G5121/2n4−2n3−35/2n2+96n−105G5181/2n4−2n3−35/2n2+91n−88G5131/2n4−2n3−35/2n2+86n−69G321/2n4−2n3−19/2n2+53n−60G451/2n4−2n3−27/2n2+67n−60G481/2n4−2n3−27/2n2+65n−52G511/2n4−2n3−35/2n2+79n−46G571/2n4−2n3−35/2n2+89n−75G5141/2n4−2n3−35/2n2+81n−56G5221/2n4−2n3−35/2n2+89n−78G5171/2n4−2n3−35/2n2+84n−63G5231/2n4−2n3−35/2n2+94n−96G5251/2n4−2n3−35/2n2+99n−112G5201/2n4−2n3−35/2n2+94n−95Lemma 6 (see [19]).
The following can be deduced from the (signless) Laplacian permanental polynomial of a graphG:(i)
The number of vertices(ii)
The number of edges(iii)
The sum of the squares of degree of vertices
We recorded the results of the sum of squares of degrees of some graphs in advance, see Table4.Table 4
The sum of squares of degrees of some graphs inGn.
Graph∑1≤i≤ndi2G20n3−2n2−7n+14G30,G32n3−2n2−11n+24G33n3−2n2−11n+22G40n3−2n2−15n+36G42,G48n3−2n2−15n+28G44,G410n3−2n2−15n+32G49n3−2n2−15n+24G52n3−2n2−19n+32G54n3−2n2−19n+50G56,G512,G515,G525n3−2n2−19n+42G58,G511,G514,G517n3−2n2−19n+36G510,G524n3−2n2−19n+44G21n3−2n2−7n+12G31n3−2n2−11n+20G34n3−2n2−11n+18G41,G45,G47n3−2n2−15n+30G43n3−2n2−15n+26G46n3−2n2−15n+34G50,G51n3−2n2−19n+34G53,G57,G513,G519,G522n3−2n2−19n+38G55,G518,G520,G523n3−2n2−19n+40G521n3−2n2−19n+30G59,G516n3−2n2−19n+46


## 3. The Proof of Theorem 1

We give some lemmas to prove Theorem1 before. First, by Lemma 6 and Table 4, we obtain a result as follows.Lemma 8.
GraphsKn, G10, G20, G21, G31, G33, G34, G40, G43, G46, G49, G52, G54, and G521 are determined by the (signless) Laplacian permanental polynomial, respectively.Lemma 9.
GraphsG30 and G32 are determined by the (signless) Laplacian permanental polynomial.Proof.
By Table4, we know that ∑i=1ndi2G30=∑i=1ndi2G32=n3−2n2−11n+24.
By Lemma4 (iv) and Table 1, we have(6)p3G30−p3G32=−13∑idi3G30−∑idi3G32+2c3G30−c3G32=4.
Furthermore, by Lemma5 (v) and Tables 1–3, we have(7)q4G32−q4G30=−14∑idi4G32−∑idi4G30+23m+1∑idi3G32−∑idi3G30+∑vivj∈EG32didj−∑vivj∈EG30didj−2∑idic3Gv32+∑idic3Gv30+2c4G32−c4G30+4mc3G32−c3G30=−6.
These imply thatG30 and G32 are not (signless) Laplacian copermanental.Lemma 10.
The following statements hold:(i)
GraphsG41, G45, and G47 are not pairwise (signless) Laplacian copermanental(ii)
GraphsG42 and G48 are not (signless) Laplacian copermanental(iii)
GraphsG44 and G410 are not (signless) Laplacian copermanentalProof.
(i)
By Lemma4 (iv) and Table 1, we get that p3G41−p3G45=4,p3G41−p3G47=2 and p3G45−p3G47=2. Furthermore, by Corollary 1 (i), Table 1, and the equations above, we obtain that q3G41−q3G45=4−4c3G41−c3G45=0,q3G41−q3G47=2−4c3G41−c3G47=2, and q3G45−q3G47=2−4c3G45−c3G47=6. Furthermore, by Lemma 5 (v) and Tables 1–3, we have q4G41−q4G45=−2. These mean that graphs G41, G45, and G47 are not pairwise (signless) Laplacian copermanental.(ii)
From Table4, we obtain that ∑i=1ndi2G42=∑i=1ndi2G48=n3−2n2−15n+28. By Lemma 4 (v) and Tables 1–3, we have p4G48−p4G42=−7. By Corollary 1 (ii), p4G48−p4G42=−7, Tables 1 and 3, and the equation above, we obtain that q4G48−q4G42=−7−4∑idic3Gv48−∑idic3Gv42+8mc3G48−c3G42=1. This implies that G42 and G48 are not (signless) Laplacian copermanental.(iii)
Similarly, by Lemma4 (iv) and Table 1, we have p3G44−p3G410=−2. By Corollary 1 (i), Table 1 and the equation above, we obtain q3G44−q3G410=−2−4c3G44−c3G410=−2. These indicate that G44 and G410 are not (signless) Laplacian copermanental.Lemma 11.
The following statements hold:(i)
GraphsG50 and G51 are not (signless) Laplacian copermanental(ii)
GraphsG53, G57, G513, G519, and G522 are not pairwise (signless) Laplacian copermanental(iii)
GraphsG58, G511, G514, and G517 are not pairwise (signless) Laplacian copermanental(iv)
GraphsG55, G518, G520, and G523 are not pairwise (signless) Laplacian copermanental(v)
GraphsG59 and G516 are not (signless) Laplacian copermanental(vi)
GraphsG510 and G524 are not (signless) Laplacian copermanental(vii)
GraphsG56, G512, G515, and G525 are not pairwise (signless) Laplacian copermanentalProof.
By Table4, we have that(8)∑i=1ndi2G50=∑i=1ndi2G51=n3−2n2−19n+34,∑i=1ndi2G53=∑i=1ndi2G57=∑i=1ndi2G513=∑i=1ndi2G519=∑i=1ndi2G522=n3−2n2−19n+38,∑i=1ndi2G55=∑i=1ndi2G518=∑i=1ndi2G520=∑i=1ndi2G523=n3−2n2−19n+40,∑i=1ndi2G56=∑i=1ndi2G512=∑i=1ndi2G515=∑i=1ndi2G525=n3−2n2−19n+42,∑i=1ndi2G58=∑i=1ndi2G511=∑i=1ndi2G514=∑i=1ndi2G517=n3−2n2−19n+36,∑i=1ndi2G59=∑i=1ndi2G516=n3−2n2−19n+46,∑i=1ndi2G56=∑i=1ndi2G512=∑i=1ndi2G515=∑i=1ndi2G525=n3−2n2−19n+42,∑i=1ndi2G58=∑i=1ndi2G511=∑i=1ndi2G514=∑i=1ndi2G517=n3−2n2−19n+36,∑i=1ndi2G59=∑i=1ndi2G516=n3−2n2−19n+46,∑i=1ndi2G510=∑i=1ndi2G524=n3−2n2−19n+44.(i)
By Lemma4 (v) and Tables 1–3, we have p4G50−p4G51=−7. By Corollary 1 (ii), Tables 1 and 3, and the equation above, we get that q4G50−q4G51=1. These mean that G50 and G51 are not (signless) Laplacian copermanental.(ii)
By Lemma4 (iv) and (v) and Tables 1–3, we get that p4G53−p4G57=−14, p3G53−p3G513=4, p3G53−p3G519=2, p3G53−p3G522=2, p3G57−p3G513=4, p3G57−p3G519=2, p3G57−p3G522=2, p3G513−p3G519=−2, p3G513−p3G522=−2, and p4G519−p4G522=−5.By Corollary1, Tables 1 and 3, and the equations above, we obtain that p4G519−p4G522=−5, q4G53−q4G513=−4, q3G53−q3G519=2, q3G53−q3G522=2, q4G57−q4G513=−6, q3G57−q3G519=2, q3G57−q3G522=2, q3G513−q3G519=2, q3G513−q3G522=2, and q4G519−q4G522=3. These imply that G53, G57, G513, G519, and G522 are not pairwise (signless) Laplacian copermanental.(iii)
Similarly, by Lemma4 (iv) and (v) and Tables 1–3, we have p3G58−p3G511=2,p3G58−p3G514=4,p3G58−p3G517=2, p3G511−p3G514=2,p3G511−p3G517=0,p4G517−p4G511=−7, and p3G514−p3G517=−2. Furthermore, by Corollary 1, Tables 1 and 3, and the equations above, we get that q3G58−q3G511=2,q4G58−q4G514=−6,q3G58−q3G517=2, q3G511−q3G514=−2,q3G514−q3G517=2, and q4G517−q4G511=1. These imply that graphs G58, G511, G514, and G517 are not pairwise (signless) Laplacian copermanental.(iv)
Similarly, by Lemma4 (iv) and (v) and Tables 1–3, we have p3G55−p3G518=2,p3G55−p3G520=2, p3G55−p3G523=0,p3G518−p3G520=0, p3G518−p3G523=−2,p3G520−p3G523=−2,p4G55−p4G523=7, and p4G518−p4G520=−1. By Corollary 1, Tables 1 and 3, and the equations above, we know that q3G55−q3G518=−2,q3G55−q3G520=2,q4G55−q4G523=−1, q3G518−q3G520=4,q3G518−q3G523=2, and q3G520−q3G523=−2. These mean that graphs G55, G518, G520, and G523 are not pairwise (signless) Laplacian copermanental.(v)
By Lemma4 (iv) and Table 1, we get that p3G59−p3G516=6. By Corollary 1 (i), Table 1, and the equation above, we have q3G59−q3G516=2. These mean that graphs G59 and G56 are not (signless) Laplacian copermanental.(vi)
By Lemma4 (iv) and Table 1, we have that p3G510−p3G524=−6. By Corollary 1 (i), Table 1, and the equation above, we obtain that q3G510−q3G524=−2. Obviously, graphs G510 and G524 are not (signless) Laplacian copermanental.(vii)
By Lemma4 (iv) and Table 1, we have p3G56−p3G512=8,p3G56−p3G515=6,p3G56−p3G525=4, p3G512−p3G515=−2,p3G512−p3G525=−4, and p3G515−p3G525=−2. Furthermore, by Corollary 1, Tables 1–3, and the equations above, we have q3G56−q3G512=4,q3G56−q3G515=6, q3G56−q3G525=4,q3G512−q3G515=2, q3G512−q3G525=6,q3G515−q3G525=−2, and q4G512−q4G525=24. Obviously, graphs G56, G512, G515, and G525 are not pairwise (signless) Laplacian copermanental.Proof of Theorem 1.
From Lemmas6–11, we directly obtain Theorem 1.



---

*Source: 9161508-2021-09-30.xml*