Virtually the same question arose in something I was working on just a few years ago. Though I didn't ask it in terms of N and k but just in terms of which regular graphs had such a perfect matching. In this case I meant for "regular" to denote that for any two vertices there is an automorphism of the whole graph taking one to the other in k "cyclically rotated" ways. I got as far as noticing that there is a perfect matching for the 5 regular polyhedra. I'm also curious about the answer for infinite regular graphs (that is, which have a perfect matching). I almost see intuitively that such must exist, but haven't written a proof. Dan
On May 31, 2015, at 5:41 AM, Allan Wechsler <acwacw@gmail.com> wrote:
I thought of this problem when musing about Wilson's grid problem.
Suppose we have a bipartite graph, with N vertices in each of two sets A and B. Further suppose that the graph is regular of degree k.
For what values of N and k can we prove that there exists a bijection f between A and B such that a vertex and its partner are always connected by an edge of the original graph? . . . . . . . . .