Permanent of the Laplacian matrix of trees and bipartite graphs (Q789402): Difference between revisions

Let \(G=(V,E)\) be a graph without loops and multiple edges with vertex set \(V=\{v_ 1,...,v_ n\}\) and edge set E. Suppose the degree of vertex \(v_ i\) equals \(d_ i\) for \(i=1,...,n\) and let \(D=D(G)\) be the diagonal matrix whose (i,i)-entry is \(d_ i\). The matrix \(L(G)=D(G)-A(G),\) where A(G) is the adjacency matrix of G, is called the Laplacian matrix of G. One of the reasons for the interest in the Laplacian matrix is the possibility of using it to distinguish non-isomorphic graphs in a way that the adjacency matrix does not. In the paper the permanent per L(G) of the Laplacian matrix L(G) is considered. The bounds for per L(G) when G is a tree, or more generally, a bipartite graph are obtained in several terms. Using the ratio of per L(G) to the product of the degrees of the vertices the lower bounds for per L(G) are obtained in the terms of the degrees of the vertices.