The Pfaffian property of circulant graphs

The importance of the Pfaffian property of a graph stems from the fact that if the graph is Pfaffian, then the number of its perfect matchings can be computed in polynomial time. A graph GG is Pfaffian if there exists an orientation of GG, denoted by G⃗, such that the determinant of the skew adjacency matrix of G⃗ equals the square of the number of perfect matchings of GG. An undirected graph G=(V,E)G=(V,E) with nn vertices is a circulant graph, denoted by Cn(a1,a2,…,am)Cn(a1,a2,…,am), if there exists a labeling of the vertices of GG, v1,v2,…,vnv1,v2,…,vn, and mm integers, a1,a2,…,ama1,a2,…,am, such that the edge set E={vivj:i−j≡±ak(modn)for  1≤k≤m}. In this paper, the Pfaffian property of circulant graphs is completely characterized, that is, a simple connected circulant graph Cn(a1,a2,…,am)Cn(a1,a2,…,am) of even order is Pfaffian if and only if m=1m=1 or, m=2m=2 and a1+a2a1+a2 is odd.