The Permanental Poiynomials Of Graphs And Related Problems

The permanent of the characteristic matrix of the adjacency matrix of a graph is said to be the permanental polynomial of the graph. In1981Kasum et al. first demonstrated that the permanental polynomials of conjugated molecules are closely related to their structures. Later, for the isomers of fullerenes, Cash computed their permanental polynomials and zeros. He found that for a given isomer series of con-stant n, the n/2pairs of zeros appear to consist of a set of10that are constant and a set of (n/2-10) that differ greatly with structure, and pointed that the permanental polynomial encodes a variety of structure information. As is well known, there are some efficient algorithms to compute determinants. However, the computation of per-manents is#P-complete. For a bipartite graph, the constant term of its permanental polynomial is equal to the square of the number of perfect matchings. If a graph G is Pfaffian, by assigning a Pfaffian orientation, we can obtain a matrix Γ by changing some1's in the adjacency matrix of G to-1's. Then the enumeration of perfect matchings of G is reduced to the computation of the determinant of Γ. According to these, Weigen Yan and Fuji Zhang proved that if G is a bipartite graph containing no even subdivision of K2,3; then there exists an orientation G of G such that the per-manental polynomial of G equals the characteristic polynomial of the skew-adjacency matrix of G.In this thesis, firstly, for the graphs whose permanental polynomials can be com-puted by the characteristic polynomials of the skew-adjacency matrices of their ori-entation graphs, we find all such graphs, characterize the structure of these graphs and provide a method to construct the above orientation. Then we compute the per-manental polynomials of some basic graphs, such as paths and cycles, and obtain the explicit expressions of the permanental polynomials of hexagonal chains and other chemical graphs. More generally, we study the permanental polynomials of matrices. We mainly characterize those matrices whose permanental polynomials can be com- puted by the characteristic polynomials of signing matrices. Finally, we discuss the constant terms of the permanental polynomials of hexagonal systems on surface i.e. the square of the number of perfect matchings. By establishing orientation graphs, we give explicit formulas on the number of perfect matchings. This thesis is divided into five chapters.In Chapter one, we introduce some basic definitions and notations, describe the investigation background and the development of permanental polynomials, and list our main results of this thesis.In the second chapter, we first prove a sufficient and necessary condition i.e. the permanental polynomial of a bipartite graph equals the characteristic polynomials of the skew-adjacency matrices of its orientation graph if and only if the bipartite graph contains no even subdivision of K2,3. Then we show that a2-connected bipartite graph contains no even subdivision of K2,3is equivalent to a planar1-cycle resonant graph. This implies that every cycle is oddly oriented in any Pfaffian orientation of a2-connected bipartite graph containing no even subdivision of K2,3.Therefore, we can compute the permanental polynomial of such a graph by Pfaffian orientation.In Chapter three, we compute the permanental polynomials of some special graphs. By the technique of Pfaffian orientation, explicit expressions for the per-manental polynomials of some basic graphs, such as a path and a cycle, are obtained. For hexagonal systems, based on reduction procedures, the permanental polynomials of hexagonal chains and a type of pericondensed hexagonal system are deduced from product of matrices of order5. Meanwhile, the permanental polynomial of a general polygonal chain is also derived.In the forth chapter, our object is characterizing those matrices whose permanen-tal polynomials can be computed by the characteristic polynomials of their signing matrices. We say that an m x n {0,1}-matrix A (m≤n) is totally convertible if there exists a matrix B (B is obtained by changing some1's in A to-1's) such that for any submatrix A' of A of order m, the corresponding submatrix B' of B satisfies that the permanental polynomial of A' equals the characteristic polynomial of B'. By associating a square {0,1}-matrix A with a bipartite graph G*A, we obtain that A is totally convertible if and only if G*A is Pfaffian. Moreover, we generalize this result to an m×n{0,1}-matrix. Then the sufficient and necessary in Chapter two is also derived by this consequence. As applications, we give the explicit expressions of the permanental polynomials of two totally convertible matrices.In Chapter five, we enumerate perfect matchings (close-packed dimers in Physics) of the honeycomb lattices on Klein bottle, Mobius strip and cylinder. By establishing a Pfaffian orientation or a crossing orientation, and then computing the determinants of the skew-symmetric matrices of the resulting orientation graphs, we obtain the ex-plicit expressions of the number of perfect matchings of Klein-bottle polyhex, Mobius polyhex and cylindrical polyhex.