tailieunhanh - Báo cáo toán học: "Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs. | Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs Feng-Gen Lin and Lian-Zhu Zhang School of Mathematical Sciences Xiamen University Xiamen 361005 E-mail zhanglz@ Submitted Dec 13 2008 Accepted Apr 14 2009 Published Apr 30 2009 Mathematics Subject Classification 2000 05A15 05C70. Abstract 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 computed in polynomial time. Although there are many equivalent conditions for the existence of a Pfaffian orientation of a graph this property is not well-characterized. The problem is that no polynomial algorithm is known for checking whether or not a given orientation of a graph is Pfaffian. Similarly we do not know whether this property of an undirected graph that it has a Pfaffian orientation is in NP. It is well known that the enumeration problem of perfect matchings for general graphs is NP-hard. L. Lovasz pointed out that it makes sense not only to seek good upper and lower bounds of the number of perfect matchings for general graphs but also to seek special classes for which the problem can be solved exactly. For a simple graph G and a cycle Cn with n vertices or a path Pn with n vertices we define Cn or Pn X G as the Cartesian product of graphs Cn or Pn and G. In the present paper we construct Pfaffian orientations of graphs C4 X G P4 X G and P3 X G where G is a non bipartite graph with a unique cycle and obtain the explicit formulas in terms of eigenvalues of the skew adjacency matrix of G to enumerate their perfect matchings by - Pfaffian approach where G is an arbitrary orientation of G. 1. Introduction The theory of Pfaffian orientations of graphs had been introduced by the physicists M. E. Fisher P W. Kasteleyn and H. N. V. Temperley. The importance of Pfaffian orientations stems This work is supposed by NFSC . .