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.
@article{10_37236_5456,
author = {Fuliang Lu and Lianzhu Zhang},
title = {A conjecture of {Norine} and {Thomas} for abelian {Cayley} graphs},
journal = {The electronic journal of combinatorics},
year = {2017},
volume = {24},
number = {3},
doi = {10.37236/5456},
zbl = {1372.05101},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5456/}
}
TY - JOUR
AU - Fuliang Lu
AU - Lianzhu Zhang
TI - A conjecture of Norine and Thomas for abelian Cayley graphs
JO - The electronic journal of combinatorics
PY - 2017
VL - 24
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/5456/
DO - 10.37236/5456
ID - 10_37236_5456
ER -
%0 Journal Article
%A Fuliang Lu
%A Lianzhu Zhang
%T A conjecture of Norine and Thomas for abelian Cayley graphs
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/5456/
%R 10.37236/5456
%F 10_37236_5456
Fuliang Lu; Lianzhu Zhang. A conjecture of Norine and Thomas for abelian Cayley graphs. The electronic journal of combinatorics, Tome 24 (2017) no. 3. doi: 10.37236/5456
