Pfaffian orientation and enumeration of perfectmatchings for some Cartesian products of graphs

摘要

The importance of Pfaffian orientations stems from the fact that if a graph G is Pfaffian,then the number of perfect matchings of G (as well as other related problems) can be com-puted in polynomial time. Although there are many equivalent conditions for the existenceof a Pfaffian orientation of a graph, this property is not well-characterized. The problem isthat no polynomial algorithm is known for checking whether or not a given orientation of agraph is Pfaffian. Similarly, we do not know whether this property of an undirected graphthat it has a Pfaffian orientation is in NP. It is well known that the enumeration problemof perfect matchings for general graphs is NP-hard. L. Lovasz pointed out that it makessense not only to seek good upper and lower bounds of the number of perfect matchingsfor general graphs, but also to seek special classes for which the problem can be solvedexactly. For a simple graph G and a cycle C, with n vertices (or a path P, with n vertices),we define C" (or P_n)x Gas the Cartesian product of graphs C, (orP_n)andG.In presentpaper, we construct Pfaffian orientations of graphs C_4 xG,P_4 xGandP_3 xG,whereGis a non bipartite graph with a unique cycle, and obtain the explicit formulas in terms of eigenvalues of the skew adjacency matrix of Chito enumerate their perfect matchings byPfaffian approach, where is an arbitrary orientation of G.