7
$\begingroup$

Petersen proved that every 2k-regular graph is 2-factorable. The factorization is in general not unique.

Given a 2k-regular graph, is it possible to move from any 2-factorization to any other 2-factorization by altering two 2-factors at a time?

If we broaden the question to multigraphs then the answer is no; consider the multigraph on three vertices with two edges between each pair of vertices and a loop on each vertex. This suggests that the answer is no even for graphs. In fact a colleague of mine suspects:

The answer is no even if we change "two" to any bounded number

(where by "two" here I mean only the number of factors being altered simultaneously, not the "2" in "2-factor"). However, we don't know how to prove or disprove this.

The motivation for this question comes from a conjecture in representation theory but the connection is rather convoluted so I will omit the details here.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

No and in fact your multigraph construction is the counterexample. Just replace each edge with an "almost 6-regular" graph, like $K_7$ minus one edge, uv, and connect u and v respectively to the endpoints of the original edge.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Nice trick, thanks! Any ideas about the followup question (replacing "two" with a bigger number)? $\endgroup$
    – Timothy Chow
    Commented Jan 25, 2013 at 15:12
  • $\begingroup$ Let me counter-question - what is known about moving between 1-factorizations of regular bipartite graphs? $\endgroup$
    – domotorp
    Commented Jan 28, 2013 at 13:27
  • $\begingroup$ Good question! I don't know, but this does seem to be a good place to start. I'll try asking on the domino mailing list. $\endgroup$
    – Timothy Chow
    Commented Jan 30, 2013 at 16:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .