Studies On Some Problems Of Permanental Polynomials Of Graphs

The permanental polynomial of a graph G is defined to be the permanent of the characteristic matrix of the adjacency matrix of G, i.e., per(xI-A(G)), where A(G) is the adjacency matrix of G, and I is the identity matrix. Valiant has proved that computing the permanent is#P-complete even when restricted to (0,1)-matrices. There are few literatures on the permanental polynomials of graphs due to the diffi-culty of actually computing the permanent. In this thesis, we consider three aspects of the permanental polynomials of graphs:determining graphs by the permanental polynomial, properties of the zeros of the permanental polynomials of graphs, and the permanental polynomials of skew adjacency matrices of oriented graphs.Morris ot al. stated that the permanental polynomial seems a little better than the characteristic polynomial when it comes to distinguishing graphs which are not trees, since they found that the permanental polynomial can distinguish five pairs of cospectral graphs. To our knowledge, no systematic studies have been made to distinguish graphs by the permanental polynomial. We first investigate whether the permanental polynomial really performs better than the characteristic polynomial when we use them to distinguish graphs which are not trees. More generally, we determine which graphs can be characterized by their permanent al polynomials, where a graph G is said to be characterized by its permanental polynomial if any graph H having the same permanental polynomial as G is isomorphic to G.We first present some characterizing properties of the permanental polynomials of graphs. Using these properties we show that complete graphs, stars, regular complete bipartite graphs and odd cycles can be determined by their permanental polynomials. Wo then prove that the paths, even cycles and lollipop graphs cannot be determined by the pennanental polynomial. However, if we restrict our attention to connected graphs, the paths, even cycles C4l/+2, odd lollipop graphs and even lollipop graphs with girth4can be determined by their pernanental polynomials.Since the permanent looks similar to the determinant, we consider whether the permanental roots (the zeros of permanental polynomial) have similar properties as the characteristic roots of graphs. We have known that the characteristic roots of graphs are all real, and the characteristic roots of a bipartite graph are symmetric with respect to the origin. It is proved that any graph has no negative permanental roots. A bipartite graph has no non-zero real permanental roots. For a graph having at least one edge, it must have complex permanental roots. Furthermore, the permanental roots of a bipartite graph are symmetric with respect to the real and imaginary axes.It is known that the skew adjacency matrix plays an important role in enumera-tion of perfect matchings. We consider the permanental polynomials of skew adjacency matrices of oriented graphs, and obtain the Sachs-type formula of the coefficients of this polynomial. Then we generalize this formula to weighted oriented graphs, which provides a graph-theoretic method to compute the permanental polynomials of real skew symmetric matrices. Furthermore, we prove that all the skew adjacency matri-ces of a graph G have the same permanental polynomial if and only if G has no even cycles, and then a graph G has no even cycles if and only if the permanental polyno-mial of Gσ equals the matching polynomial of G for all orientations Gσ. Finally, the relationship of permanental roots of G and Gσ is investigated.