关键词: 凯莱图, 双循环群, Pfaffian性, 平面性

Abstract:

The Pfaffian property of graphs is of fundamental importance in graph theory, as it precisely characterizes those graphs for which the number of perfect matchings can be computed in polynomial time with respect to the number of edges. The study of Pfaffian graphs originated from the enumeration of perfect matching in planar graphs. References \cite{4,5,7} demonstrated that every planar graph is Pfaffian. Therefore, the Pfaffian property and planarity of graphs play a vital role in modern matching theory.

This paper contributes a complete characterization of the Pfaffian property and planarity of connected Cayley graphs over the dicyclic group $T_{4n}$ of order $4n$ $(n\geq 3)$, shows that the Cayley graph $Cay(T_{4n}, S)$ is Pfaffian if and only if $n$ is odd and $S=\{a^{k_1},a^{2n-k_1},ba^{k_2},ba^{n+k_2}\}$, where $1\leq k_1\leq n-1$, $0\leq k_2\leq n-1$ and $(k_1,n)=1$, and furthermore, shows that $Cay(T_{4n}, S)$ is never planar.

Key words: Cayley graph, Dicyclic group, Pfaffian property, Planarity