Though as I just realized I was not assuming any bipartiteness of the graph. —Dan
On May 31, 2015, at 5:55 AM, Dan Asimov <asimov@msri.org> wrote:
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? . . . . . . . . .
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun