2
$\begingroup$

Let $G=(X,Y,E)$ be an $r$-regular bipartite graph where $|X|=|Y|$ . Let $\phi$ an automorphism of $G$ with $\phi(X) = Y$ and $\phi \circ \phi = id$, and let $\psi$ be the mapping induced by $\phi$ on the edges of $G$.

Does $G$ have a matching $M$ such that $\psi(M) \cap M = \emptyset$ ? If so, how many of them it takes to cover the edges of $G$?

$\endgroup$
4
  • $\begingroup$ Do you want $r \geq 2$? Otherwise take $G$ to be a single matching with the `edge endpoint reversing' automorphism. $\endgroup$ May 22, 2012 at 1:55
  • $\begingroup$ Also, is $M$ required to be a perfect matching? There are none if $|X|$ is odd. $\endgroup$ May 22, 2012 at 2:00
  • $\begingroup$ The phrasing says "homework". Voting to close. $\endgroup$
    – Igor Rivin
    May 22, 2012 at 2:03
  • $\begingroup$ $r \geq 3$ and $M$ is indeed a perfect matching. @Igor Rivin this is not a Homowork. I am interested in 1-factorizations of bipartite regular graphs when extra conditions on the graphs are imposed. $\endgroup$
    – hbm
    May 22, 2012 at 16:05

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.