4
$\begingroup$

Let $G(V,E)$ be a graph with a 1-factorizations $M$ and $m=|M|$ 1-factors. I am searching for graphs with unique 1-factorizations (i.e. there is only one 1-factorization).

Examples:

(Some graphs have unique 1-factorizations under isomorphism, such as the 3-prism graph $Y_3$, but I am not interested in those.)

  1. Are there other examples?
  2. What is the maximum number $m$ of 1-factors, when $G$ has a unique 1-factorization?

I conjecture that the answer to question 2 is $m=3$ (for $K_4$), but I don't know how to prove that.

I would be very happy for every hint to an answer or a relevant literature.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
9
$\begingroup$

If there is only one edge colouring with $k$ colours of a graph with chromatic index $k$, the graph is said to be "uniquely edge colourable". If you search on that phrase (with and without the second "u") you will find that the problem is trivial for $k\le 2$, solved for $k\ge 4$ (only case $K_{1,k}$) and for $k=3$ can be reduced to the case of cubic graphs. For example, see this paper of Andrew Thomason. It is said that an example is the generalized Petersen graph $P(9,2)$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you very much for this answer! The P(9,2) is a wonderful counterexample for a conjecture I had (actually, something I believed was obviously true): A perfect matching is always a 1-factor (one factor of a complete 1-factorization). Apparently, the P(9,2) has a perfect matching connecting all inner vertices with the outer ones. And that one is no 1-factor. Thank you very much! $\endgroup$
    – Mario Krenn
    Commented Apr 11, 2017 at 16:19
  • $\begingroup$ I tried searching without the second "u" but didn't find anything on "uniqely edge colurable"! $\endgroup$
    – Gordon Royle
    Commented Apr 11, 2017 at 22:52
  • 1
    $\begingroup$ @GordonRoyle : Smart arse. $\endgroup$
    – Brendan McKay
    Commented Apr 12, 2017 at 4:47
  • $\begingroup$ @BrendanMcKay After your answer I had to think again what I actually needed, and finally reformulated the question. Thank you very much again, your answer was very helpful! $\endgroup$
    – Mario Krenn
    Commented Apr 12, 2017 at 13:16
3
$\begingroup$

This is just to expand a little bit on Brendan's answer.

For cubic graphs, there is a construction that gives a large number of uniquely 3-edge colourable graphs: start with $K_4$, and repeatedly insert a vertex of degree 3 into a triangular face. This gives a bunch of uniquely-4-colourable planar triangulations (in fact, it is known that this family contains all the uniquely-4-colourable planar triangulations) so the duals of these graphs form a large class of uniquely 3-edge colourable cubic graphs.

Of course, all of these graphs are planar and so at one stage, some optimist conjectured that this was the entire collection of uniquely 3-edge colourable cubic graphs. The $P(9,2)$ example referred to in Brendan's answer is the smallest non-planar cubic graph that is uniquely 3-edge colourable, though lots more such graphs are known.

Related to all this is the question of when a cubic graph has exactly 3 Hamilton cycles. Certainly any uniquely 3-edge colourable cubic graph has exactly 3 Hamilton cycles, but the converse is not true. Thomason found a family of cubic graphs (more generalised Petersen graphs) with exactly 3 Hamilton cycles that are not uniquely 3-edge colourable. The smallest of Thomason's examples is $P(15,2)$ and I wonder if this is actually the smallest possible example. Before you ask, Brendan, I have checked up to 26 vertices, so there might be some examples hiding on 28 vertices but no smaller.

Improve this answer
$\endgroup$

You must log in to answer this question.

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