4
$\begingroup$

Definition: Let $MH(n)$ be the maximal number of perfect matchings (1-regular graphs) on $n$ vertices where the union of any two perfect matchings is a Hamiltonian cycle.

Question: Is it true that $MH(N)=n-1$ for infinitely many $n$?

Additional information: Needless to say that the problem makes sense only when $n$ is even. I needed in a proof that $3 \leq MH(n)$. This is true and not hard, but right now I can prove it by two simple constructions, one when $n=4k$ and an other when $n=4k+2$. So I am just curious what might be the maximal possible number.

It is easy to see that $MH(N)\leq n-1$ since the perfect matchings must be edge disjoint and there are not enough edges for more than $n-1$. It is very easy to see that $MH(4)=3$. But I was quite surprised when it turned out that $MH(6)=5$. See the picture for the construction, it is not hard to check that indeed every pairwise union forms a Hamiltonian path. So right now it is still possible that $MH(n)=n-1$ for all even $n$.

The 5 matchings on 6 vertices

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ If you have $n-1$ of these one-factors, then you have a "perfect one-factorisation of the complete graph". My dated understanding is that it is an open question as to whether they exist for all even n, but searching on this phrase should help. $\endgroup$
    – Gordon Royle
    Commented Dec 30, 2016 at 6:55
  • $\begingroup$ @GordonRoyle Oh, so this is already studied and is called perfect one-factorisation. And indeed it seems to be open. Thank you very much! Should I delete the question? $\endgroup$
    – Daniel Soltész
    Commented Dec 30, 2016 at 7:02
  • $\begingroup$ I don't think you need to delete, it would be interesting to know the state of the art. (But certainly they exist infinitely often.) $\endgroup$
    – Gordon Royle
    Commented Dec 30, 2016 at 7:12

1 Answer 1

Reset to default
4
$\begingroup$

Assume that $n-1$ is an odd prime. Arrange the vertices as follows: $n-1$ of them lie on the circle and form a regular $(n-1)$-gon, and the $n$th vertex is the center. Now, each of the matchings consists of one radius and all the chords perpendicular to this radius.

Indeed, take any two matchings and remove the two radii. The remaining egdes form a graph with two vertices of degree 1 and all the rest of degree 2. Moreover, since $n-1$ is prime, it is easy to see that this graph contains no cycles (such cycle should pass through all the vertices which is impossible). Thus this graph is a path, and the radii complete a Hamiltonian cycle.

Right now I do not know what happens if $n-1$ is composite.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

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