# Computing the Permanent of the Laplacian Matrices of Nonbipartite Graphs

Authors: Xiaoxue Hu; Grace Kalaso
Journal: Journal of Mathematics
 (2021)

---

## Abstract

LetG be a graph with Laplacian matrix LG. Denote by perLG the permanent of LG. In this study, we investigate the problem of computing the permanent of the Laplacian matrix of nonbipartite graphs. We show that the permanent of the Laplacian matrix of some classes of nonbipartite graphs can be formulated as the composite of the determinants of two matrices related to those Laplacian matrices. In addition, some recursion formulas on perLG are deduced.


---

## Body

## 1. Introduction

All graphs in this paper are restricted to be simple. LetG=VG,EG be a connected simple graph with vertex set VG=1,2,…,n and edge set EG. Denoted by dGv, or short for dv if there is no confusion, the degree of v∈VG. Let G be a graph of order n. The adjacency matrix A=AG=aijn×n related to G is defined as aij=1 if and only if i and j are adjacent and 0 otherwise. Let D=DG be the diagonal matrix of the graph G whose i,i entry is di,i=1,2,…,n. The Laplacian matrix related to G is defined by LG=DG−AG, which has been extensively investigated for a long time. For more properties of the Laplacian matrix of graphs, reader may refer to the books [1, 2], the surveys [3–5], and the references therein.The determinant and permanent of ann×n square matrix A=aijn×n is defined by(1)detA=∑sgnσ∏i=1nai,σi,perA=∑∏i=1nai,σi,respectively, where the summation extends over all permutations σ of 1,2,…,n and sgnσ=1 if σ is the product of an even number of transpositions and sgnσ=−1 otherwise.The formula for permanent is similar to, even simpler than, the formula for determinant. However, there is a polynomial algorithm for calculating determinants, whereas calculating permanents is#P-complete as shown by Valiant [6]. Therefore, it is reasonable to ask if perhaps computing the permanent of a matrix can be somehow converted to computing the determinant of a related matrix. Readers may refer to [7–9] and the references therein for more information on this question.There are many results on the permanent, or the permanent polynomialperIλ−A, in terms of the adjacency matrix of bipartite graphs, see, for example, [10, 11], whereas, there are few formulaic results on the permanent of the matrix related to the nonbipartite graphs.Merris et al. [12] first studied the permanent of the Laplacian matrix, in which the polynomial perxI−LG is suggested to distinguish nonisomorphic trees, and lower bounds on the permanent of LG, perLG, were conjectured. After that, several lower bounds on perLG were proved by Brualdi and Goldwasser [13] and Merris [11]. For more results on the permanent of the Laplacian matrix, we refer the reader to [11–15] and the references contained therein.Pólya’s permanent problem is well known, which has many equivalent versions, such as, given a matrixA, it was possible to change the signs of some of the entries of A to give a new matrix B such that the corresponding terms of perA and detB were equal. Pólya’s permanent problem still remains open. We refer the readers to the survey [16] for the history and different versions of Pólya’s permanent problem.In general, for Pólya’s permanent problem, we only consider exactly one objective matrix, that is, for a given matrix A, we want to find one objective matrix B related to A such that perA=detB. Naturally, the following question, which can be considered as a generalized version Pólya’s permanent problem, is interesting.For a given matrixA, can we find two matrices B and C related to A such that perA is the composite of detB and detC?We, in this paper, continue to investigate the problem of computing the permanent of the Laplacian matrix of graphs. In Section2, we give some preliminary results, including the combinatorial description of perLGσ and perLiG in terms of Sachs subgraphs, where Gσ is an oriented graph defined in below and LiG=DG−AGi with i2=−1. In Section 3, we first deduce a formula on the permanent of the Laplacian matrix of a class of bipartite graphs. Then, we show that the permanent of the Laplacian matrix of a class of nonbipartite graphs can be formulated as the composite of the determinants of two matrices related to their Laplacian matrices. In addition, some recursion formulas on perLG are obtained, which can simplify the calculation on the permanent of the Laplacian matrix of more general classes of nonbipartite graphs.


## 2. Preliminary

LetG be a connected graph with vertex set V and edge set E. An edge e∈E is called a bridge if the resultant graph obtained from G by deleting the edge e has two components. For a nonempty subset W of VG, the subgraph with vertex set W and edge set consisting of those pairs of vertices that are edges in G is called the induced subgraph of G, denoted by GW. Denote by G\U, where U⊆V, and the graph is obtained from G by removing the vertices of U together with all edges incident to them. Let LiG=DG−AGi, where DG and AG are defined as above and i2=−1.LetG be a graph with vertex set V=1,2,…,n. The matrix M=mijn×n is called a graphical matrix of G if mij≠0, i≠j, if and only if i,j is an edge of G. Then, the adjacency matrix AG, the Laplacian matrix LG, and the matrix LiG are all graphical matrices with respect to the given graph G. Let G be a graph and M be a graphical matrix of G. Suppose that e=i,j is an edge of G and G1 is a subgraph of G. Denote by MG\e the matrix obtained from M by replacing the entries mij and mji by zeros, and by MG1 the principle submatrix of M corresponding to the subgraph G1. Then, MG\e (resp. MG1) is a graphical matrix of G\e (resp. G1) if and only if M is a graphical matrix of G.For an undirected graphG, the subgraph H of G is called a Sachs subgraph of G if each component of H is either a single edge or a cycle; see, for instance, [16]. For a Sachs subgraph H, denote, by coH and cH, the number of odd cycles and cycles contained in H, respectively.An oriented graphGσ is a graph obtained from an undirected graph G by orienting each edge of G a direction. Then, G is referred as the underlying graph of Gσ. We should point out that our oriented graph considered its underlying graph in terms of defining matching, degree, path, and connectedness. An even oriented cycle C in Gσ is called oddly oriented (resp. evenly oriented) if, for either choice of direction of traversal around C, the number of edges of C directed in the direction of traversal is odd (resp. even). Clearly, this is independent of the initial choice of direction of traversal. An oriented graph Gσ is Pfaffian if every even oriented cycle of G is oddly oriented in Gσ. A graph is called Pfaffian if such a graph has a Pfaffian orientation, see [16].LetGσ be an oriented graph with vertex set VGσ=1,2,…,n. The adjacency matrix AGσ=aijn×n of Gσ is defined as aij=−aji=1 if ij is an edge of Gσ with tail i and head j and aij=0, otherwise. The Laplacian matrix LGσ of Gσ is defined as LGσ=DGσ−AGσ, where DGσ is the degree diagonal matrix of its corresponding underlying graph G. Obviously, LGσ is a graphical matrix of Gσ, as well as of G. We refer to [17, 18] and the references therein for more spectral properties on the adjacency matrix of oriented graphs.The subgraph, denoted byHσ, of a given oriented graph Gσ is called a Sachs oriented subgraph of Gσ if each component of Hσ is either a single edge or a cycle with length even; see examples [18]. For a given Sachs oriented subgraph Hσ, denote by c+Hσ and cHσ the number of evenly even cycles and cycles contained in Hσ, respectively.For a given oriented graphGσ, an argument similar to the one given in the proof of Theorem 2.1 in pp. 276–277 of [11] yields the combinatorial description of detLGσ; for completeness, we give a simple proof.Theorem 1.
LetGσ be a graph of order n and LGσ be its Laplacian matrix. Then,(2)detLGσ=∑K⊆1,2,…,n∑Hσ∈HKσ−1c+Hσ2cHσ∏i∉Kdi,where the first summation is over all induced subgraphs Kσ of Gσ, the second summation is over all Sachs spanning subgraph Hσ of Kσ, and c+Hσ and cHσ are defined as above.Proof.
Note thatLGσ=DGσ−AGσ; then, by the Laplace expansion formula,(3)detLGσ=∑K⊆1,2,…,n−1KdetAKdetGσ\K,where the summation is over all induced subgraphs Kσ of Gσ. Similar to the proof in Theorem 2.3 of [18],(4)−1KdetAK=∑Hσ∈HKσ−1c+Hσ2cHσ,detGσ\K=∏i∉Kdi,where the summation is over all Sachs spanning subgraph Hσ of Kσ and c+Hσ and cHσ are defined as above. Consequently, the proof is complete.
Denote byωH the number of components contained in H. Similarly, we can obtain the following result.Theorem 2.
LetG be a graph of order n and LiG=DG−AGi. Then,(5)detLiG=∑K⊆1,2,…,n−iK∑H∈HK−1ωH2cH∏i∉Kdi,where the first summation is over all subgraphs K of G, the second summation is over all Sach spanning subgraph H of K, and cH denotes the number of cycles contained in H.


## 3. The Permanent of the Laplacian Matrix of a Graph

From the work of Brualdi and Goldwasser [13], a formula on the permanent of the Laplacian matrix of a graph is given as follows.Lemma 1 (see Lemma 2.1 in [13]).
LetG be a graph of order n and LG be its Laplacian matrix. Then,(6)perLG=∑K⊆1,2,…,n∑H∈HK−1coH2cH∏i∉Kdi,where the first summation is over all induced subgraphs K of G, the second summation is over all Sachs spanning subgraph H of K, and coH and cH denote the number of odd cycles and cycles contained in H, respectively.Combining with Theorem1 and Lemma 1, we have the following theorem.Theorem 3.
LetG be a bipartite Pfaffian graph of order n and let σ be an orientation of G such that Gσ is a Pfaffian oriented graph. Let LG and LGσ be the Laplacian matrices of G and Gσ, respectively. Then,(7)perLG=detLGσ.Proof.
LetH be any Sachs subgraph of G and the corresponding Sachs oriented subgraph of Gσ be denoted by Hσ. Since G is bipartite, the order of H is even and CoH=0. Thus,(8)−1coH2cH∏i∉Hdi=2cH∏i∉Hdi.
SinceGσ is Pfaffian, then Hσ is Pfaffian and c+Hσ=0. Thus,(9)−1c+Hσ2ceHσ∏i∉Hσdi=2ceHσ∏i∉Hσdi,where ceHσ denotes the number of all even cycles contained in Hσ. Consequently, the result is as follows.
Theorem3 is invalid to graphs containing odd cycles. Roughly speaking, any odd cycle has no contribution to the determinant of the Laplacian matrix of an oriented graph. However, for the permanent of the Laplacian matrix of an undirected graph, the effect of odd cycles is completely different. Henceforth, it is difficulty to compute the permanent of the Laplacian matrix of a nonbipartite graph.
In the following, we will show that there exists a class of nonpartite graphs such that the permanent of the Laplacian matrix of those graphs can be formulated as the composite of the determinants of two matrices related toLG.
LetG1 be the set of all Pfaffian graphs in which each element G of G1 satisfies the following:(1)
Each odd cycle contained inG has length 3mod4(2)
G contains no disjoint odd cycles, that is, two arbitrary odd cycles have at least one common vertex(3)
For any odd cycleC, G∖C contains no cycles with length 0mod4Theorem 4.
LetG be a graph with u∈VG. Then,(10)perLG=perLG\udGu+∑eincident touperLG\e+2∑u∈C−1CperLG\C,where the first summation is over all edges incident to u and the second summation is over all cycle C containing the vertex u.Proof.
All Sachs subgraphs ofG can be divided into three kinds: those that contain the edge e, incident to the vertex u, as a single edge, those that contain u as a vertex of a cycle, and those that do not. One finds that the sum of all summands of the former is per∑eLG\e, the sum of all summands of the second kind is 2∑u∈C−1CperLG\C, and the sum of all summands of the third kind is perLG\udGu. Thus, the result is as follows.Theorem 5.
LetG be a graph with e=u,v∈EG. Then,(11)perLG=perLG\u,v+perLG\e+2∑e∈C−1CperLG\C,where the summation is over all cycle C containing the edge e.Proof.
All Sachs subgraphs ofG can be divided into three kinds: those that contain the edge e as a single edge, those that contain e as an edge of a cycle, and those that do not. One finds that the sum of all summands of the former is perLG\u,v, the sum of all summands of the second kind is 2∑e∈C−1CperLG\C, and the sum of all summands of the third kind is perLG\e. Thus, the result is as follows..
As a consequence of Theorem5, we have the following result.Corollary 1.
LetG1 and G2 be two disjoint graphs with u∈G1 and v∈G2, and G be the graph obtained from G1 and G2 by adding an edge between u and v. Then,(12)perLG=perLG1perLG2+perLG1\uperLG2\v.



---

*Source: 6621029-2021-06-23.xml*