Skip to main content
4 of 5
In response to a question added by the OP during a recent edit, I added--with reference--the usual technical term for what the OP called 'panfactorial' (i.e. 'every edge is contained in a perfect matching')..
Peter Heinig
  • 6.1k
  • 1
  • 27
  • 47

How to characterize "matching-transitive" regular graphs?

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.

Wolfgang
  • 13.4k
  • 5
  • 45
  • 102