Enumeration of perfect matchings of the Cartesian products of graphs (Q2699650)

Summary: A subgraph \(H\) of a graph \(G\) is nice if \(G-V(H)\) has a perfect matching. An even cycle \(C\) in an oriented graph is oddly oriented if for either choice of direction of traversal around \(C \), the number of edges of \(C\) directed along the traversal is odd. An orientation \(D\) of a graph \(G\) with an even number of vertices is Pfaffian if every nice cycle of \(G\) is oddly oriented in \(D \). Let \(P_n\) denote a path on \(n\) vertices. The Pfaffian graph \(G \times P_{2n}\) was determined by \textit{F. Lu} and \textit{L. Zhang} [J. Comb. Optim. 27, No. 3, 530--540 (2014; Zbl 1322.90078)]. In this paper, we characterize the Pfaffian graph \(G \times P_{2n+1}\) with respect to the forbidden subgraphs of \(G\). We first give sufficient and necessary conditions under which \(G\times P_{2n+1}\) \((n\geqslant 2)\) is Pfaffian. Then we characterize the Pfaffian graph \(G \times P_3\) when \(G\) is a bipartite graph, and we generalize this result to the case \(G\) contains exactly one odd cycle. Following these results, we enumerate the number of perfect matchings of the Pfaffian graph \(G \times P_n\) in terms of the eigenvalues of the orientation graph of \(G\), and we also count perfect matchings of some Pfaffian graph \(G \times P_n\) by the eigenvalues of \(G\).