The Pfaffian Property Of Graphs And The Enumeration Problem Of Perfect Matchings

Suppose M is a perfect matching of graph G,and suppose M(G)is the set of all perfect matchings of G.The enumeration problem of perfect matchings(i.e.counting the order of M(G))in graphs is a central problem in the graph theory.However,Valiant proved that counting the number of perfect matchings in general graphs(even in bipartite graphs)is#P-complete.Fortunately,if G is a Pfaffian graph,then the number of perfect matchings of G(as well as other related problems)can be computed in polynomial time.Where G is called Pfaffian if it has a Pfaffian orientation,namely it admits an orientation such that the number of edges of any M-alternating cycle which have the same direction as the traversal direction is odd for some perfect matching M of the graph.Kasteleyn proved that every planar graph is Pfaffian.For non-planar graphs,the problem of recognizing Pfaffian graphs is more complicated.In 1975,Little charac-terized the structure of Pfaffian bipartite graphs.Furthermore,McCuaig and,indepen-dently,Robertson,Seymour and Thomas found an algorithm which decides whether a bipartite graph is Pfaffian in time O(n3).On the other hand,the complexity of distin-guishing general Pfaffian graphs remains an intriguing open problem.In this thesis,we study the Pfaffian properties of some graphs and its application on enumerating the number of perfect matchings in graphs.It is partitioned into five chapters.In Chapter 1,we collect some basic definitions and notations,introduce the back-ground of Pfaffian orientations,known results,and related problems,and introduce the main results of this thesis.In Chapter 2,we obtain a necessary and sufficient condition of Pfaffian bipartite graphs with maximum degree at least |V(G)|/2-1.Then,we design an O(|E(G)|2)algorithm for recognizing Pfaffian graphs in this class and constructs a Pfaffian orien-tation if the graph is Pfaffian.The results improve and generalize some known results.In Chapter 3,we obtain a sufficient condition of Pfaffian graphs on torus.More specific,we prove that for a non-bipartite graph embedding on the torus,if the bound-aries of all faces are even,then it is Pfaffian.The results improve and generalize some known results.In Chapter 4,we obtain some explicit expressions of the number of perfect match-ings for two types of lattices(8.6.4 lattice and 8.8.4 lattice)with toroidal boundary.Furthermore,we obtain their entropies.In Chapter 5,we obtain the explicit expressions of the number of perfect match-ings of some honeycomb lattices on Klein bottle and Mobius strip.