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$?

Improve this question
$\endgroup$
4
  • $\begingroup$ Do you want $r \geq 2$? Otherwise take $G$ to be a single matching with the `edge endpoint reversing' automorphism. $\endgroup$
    – Michael Albert
    Commented May 22, 2012 at 1:55
  • $\begingroup$ Also, is $M$ required to be a perfect matching? There are none if $|X|$ is odd. $\endgroup$
    – Brendan McKay
    Commented May 22, 2012 at 2:00
  • $\begingroup$ The phrasing says "homework". Voting to close. $\endgroup$
    – Igor Rivin
    Commented 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
    Commented May 22, 2012 at 16:05

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .