The Pfaffian property of Cayley graphs on dihedral groups (Q2197482)

If \(G\) is a group with identity element 1, and \(S\) is any subset of elements with \(1\notin S\) which is closed under the taking of inverses, the authors define the Cayley graph \(\Gamma(G,S)\) as the directed graph on vertex set \(G\), where an edge connects vertex \(x\) to vertex \(y\) iff \(x^{-1}y\in S\); caveat lector: the authors' definition does not require that \(S\) be a set of generators, or even that it be nonempty! For basic properties of Pfaffian orientations, the authors suggest [\textit{R. Thomas}, in: Proceedings of the international congress of mathematicians (ICM), Madrid, Spain, August 22--30, 2006. Volume III: Invited lectures. Zürich: European Mathematical Society (EMS). 963--984 (2006; Zbl 1101.05054)]; \(\mathbb{Z}_n(a_1,\dots,a_m),\left(a_1,\dots,a_m\in\left[0,\frac n2\right]\right)\) denotes the circulant graph with vertices \(v_1,v_2,\dots,v_n\) labelled with the integers modulo \(n\) and edge-set \(\{v_iv_j:i-j\equiv\pm a_k \pmod n,1\le k\le m\}\). \par In this paper, the authors characterize the Pfaffian property of Cayley graphs on dihedral groups: Theorem 14 states that if \(\Gamma(D_n,S)\) is a connected Cayley graph on a dihedral group \(D_n\) of order \(2n\), then \(\Gamma(D_n,S)\) is Pfaffian if and only if it is isomorphic to one of the following graphs ``or its spanning subgraph'' (sic): (1) the Cartesian product of \(\mathbb{Z}_{2n}(1,2n-1,n)\) and a path of length 2, where \(n\) is even; (2) the Heawood 6-cage; (3) the Cayley graph \(\mathbb{Z}_{2n}(s,t)\), where \(s+t\) is odd; (4) the Cartesian product of the cycle graphs of orders \({\frac n2}\) and \(4\), where \(\frac n2\) is odd.