The Pfaffian property of Cartesian products of graphs.

Suppose that G=( V, E) is a graph with even vertices. An even cycle C is a nice cycle of G if G− V( C) has a perfect matching. An orientation of G is a Pfaffian orientation if each nice cycle C has an odd number of edges directed in either direction of the cycle. Let P and C denote the path and the cycle on n vertices, respectively. In this paper, we characterize the Pfaffian property of Cartesian products G× P and G× C for any graph G in terms of forbidden subgraphs of G. This extends the results in (Yan and Zhang in Discrete Appl Math 154:145-157, 2006). [ABSTRACT FROM AUTHOR]