A Conjecture of Norine and Thomas for Abelian Cayley Graphs

Abstract

A graph $\Gamma_1$ is a matching minor of $\Gamma$ if some even subdivision of $\Gamma_1$ is isomorphic to a subgraph $\Gamma_2$ of $\Gamma$, and by deleting the vertices of $\Gamma_2$ from $\Gamma$ the left subgraph has a perfect matching. Motivated by the study of Pfaffian graphs (the numbers of perfect matchings of these graphs can be computed in polynomial time), we characterized Abelian Cayley graphs which do not contain a $K_{3,3}$ matching minor. Furthermore, the Pfaffian property of Cayley graphs on Abelian groups is completely characterized. This result confirms that the conjecture posed by Norine and Thomas in 2008 for Abelian Cayley graphs is true.