I am interested in regular graphs $G$ such that for each pair of 1-factors (=perfect matchings) $F$ and $F'$ there is an automorphism of $G$ that takes $F$ to $F'$. Let's call this property ** matching transitivity**.

Those graphs should have a fairly big automorphism group. **I am wondering whether it is possible to characterize them.**

Trivial examples of matching-transitive graph are $K_{2n}$ or the complete bipartite graph $K_{n,n}$.

*EDITED** after Brendan McKay's comment*:

If we remove successively 1-factors from such a graph, it is ~~clear~~ *not true* that this property is maintained at each stage.

The question is inspired by the existence of graphs whose 2-factors are isomorphic (as graphs), i.e. all have the same partition $\pi$ as cycle type. For a discussion and examples of such graphs for various cycle types see here and here. All those graphs are cubic, and BTW I don't think that such a graph can be $k$-regular with $k>3$. (Is there an easy argument for that?)

Some of those graphs have lots of symmetries, others a rather small automorphism group, like for instance, the graph of type $(5,11)$ given in this answer, which has a unique triangle and automorphism group $S_3$, but not less than $12$ different 1-factors (so it cannot be matching-transitive). On the other hand, the Heawood graph ($|Aut(G)|=336$) is, and so is the Coxeter Graph (same automorphism group) as outlined here.

**EDIT**: As mentioned in another comment, there are many graphs with a unique perfect matching, which is obviously not what I am after. So I'll add the (somewhat mild) condition that each edge should belong to some perfect matching. Such a graph is called *$1$-extendable* (cf. page 113 in [László Lovász, Michael D. Plummer, *Matching Theory*, Annals of Discrete Mathematics 29, North-Holland, 1986, ISBN: 0 444 87916 1]).

So:

For given $n$ and $k$, can anything be said about the matching-transitivity of a connected $1$-extendable $k$-regular graph on $n$ vertices in terms of the size (or structure) of its automorphism group?

Note that both Heawood and Coxeter Graph are indeed $1$-extendable, and so is the $(5,11)$ graph mentioned before. There is possibly more hope now that, roughy speaking, the bigger the automorphism group, the bigger the chance for the graph to be matching-transitive.

regulargraph, it should be pointed out that there is even less hope to characterizeallmatching-transitive graphs, for the simple fact that there is a bewildering variety ofgraphs with a unique perfect matching, and all of those are matching-transitive no matter what their automorphism group is. While there are some results about the structure of graphs with a unique p.m., there is nothing like an appreciable characterization of them, and a char. of all matching-transitive graphs would have to encompass all of those. $\endgroup$ – Peter Heinig Mar 17 '18 at 10:429more comments