Return to Question

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, 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.

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.

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. Let's call such a graph pan-factorial. (Is there a nicer name?)

So:

For given $n$ and $k$, can anything be said about the matching-transitivity of a connected pan-factorial $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 pan-factorial, 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.

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, 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.

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.

For instance if we start with a matching-transitive graph (e.g. $K_{2n}$ or the complete bipartite graph $K_{n,n}$) and remove successively 1-factors from it, it is clear that this property is maintained at each stage. Note that if the graph has an odd cycle, we may arrive at a stage where the resulting graph has no more 1-factors, but then the notion is moot anyway, so we will exclude the graphs corresponding to those ultimate stages.

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.

So:

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

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. Let's call such a graph pan-factorial. (Is there a nicer name?)

So:

For given $n$ and $k$, can anything be said about the matching-transitivity of a connected pan-factorial $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 pan-factorial, 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.