Enumeration Of Perfect Matchings Of P₃×T

A perfect matching of a graph G is a set of independent edges of G covering all vertices of G.So far,many mathematicians,physicists and chemists have given most of their attention to counting perfect matchings of graphs.The Pfaffian method was first discovered by Kasteleyn to enumerate perfect matchings in planar graphs.We denote the path with m vertices by P_m and a tree by T and the Cartesian product of graphs G and H by G×H.If T has a perfect matching,W. Yan,F.Zhang obtained a formula to enumerate perfect matchings of P₃×T by the Pfaffian method in[W.Yan and F.Zhang,Enumeration of perfect matchings of a type of Cartesian products of graphs,Discrete Appl.Math.154(2006) 145-157],and they posed the following problem:Suppose that T is a tree with even number of vertices containing no perfect matching,enumerate perfect matchings of P₃×T.In this paper,we characterize the perfect matchings of P₃×T and give a Pfaffian orientation of it no matter whether T has a perfect matching or not,and obtain the formula to enumerate perfect matchings of P₃×T for some types of T.