Perfect partition of some regular bipartite graphs

Abstract

A graph has a perfect partition if all its perfect matchings can be partitioned so that each part is a 1-factorization of the graph. Let $L_{rm,r}=K_{rm,rm}-m{K}_{r,r}$. We first give a formula to count the number of perfect matchings of $L_{rm,r}$, then show that $L_{6,1}$ and $L_{8,2}$ have perfect partitions.

11 pages, 1 figure