0
$\begingroup$

Petersen proved that every 2k-regular graph can be decomposed into k disjoint 2-factors. I would like to know that is it true that if G is a directed regular graph (d_out(v)=d_in(v)=k), then can G be decomposed into k directed 2-factors? And if it is true where can I find a proof for it?

$\endgroup$
1
$\begingroup$

It is true. In order to find a 2-factor in a regular directed graph, you need to associate an outneighbour to any vertex, in such a way that two vertices select different outneighbours.

Use Hall's theorem to obtain that. Hall's theorem always works on regular bipartite graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.