9
$\begingroup$

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.

Improve this question
$\endgroup$
14
  • 3
    $\begingroup$ Is there a non $K_{2n}$, non $K_{n,n}$ example of a matching transitive graph of degree at least $3$? $\endgroup$
    – Katja Berčič
    Commented Mar 16, 2018 at 16:48
  • $\begingroup$ For $n\ge 8$, $K_n$ minus one 1-factor is not an example (so what you say is clear is not true). Consider three 1-factors in $K_8$, $M_1,M_2,M_3$ such that $M_1\cup M_2$ is an 8-cycle and $M_1\cup M_3$ is two 4-cycles. Then there is no automorphism of $K_8-M_1$ that maps $K_2$ onto $K_3$, since such a permutation would map an 8-cycle of $K_8$ onto two 4-cycles. $\endgroup$
    – Brendan McKay
    Commented Mar 17, 2018 at 1:08
  • $\begingroup$ @KatjaBerčič : the disjoint union of equal $K_{2n}$s or $K_{n,n}$s. But your question is good if connectivity is required. $\endgroup$
    – Brendan McKay
    Commented Mar 17, 2018 at 1:11
  • $\begingroup$ Take two copies of $K_4$. Insert a new vertex $x$ into an edge of one copy, and a new vertex $y$ into an edge of the other copy. Then join $x$ and $y$. I believe you get a 3-regular graph of order 10 with 4 equivalent 1-factors. $\endgroup$
    – Brendan McKay
    Commented Mar 17, 2018 at 2:25
  • $\begingroup$ Recognizing that the OP's question in the gray box focuses on regular graph, it should be pointed out that there is even less hope to characterize all matching-transitive graphs, for the simple fact that there is a bewildering variety of graphs 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
    Commented Mar 17, 2018 at 10:42

2 Answers 2

Reset to default
3
$\begingroup$

One infinite family is the lexicographic product (composition) $C_s[\bar K_t]$, where $s$ is odd and $t$ is even. Basically you take the cycle $C_s$ and expand each vertex into a cluster of $t$ independent vertices. Here is $C_5[\bar K_2]$ with a representative perfect matching. In general, any perfect matching has $t/2$ edges between each consecutive cluster of vertices. Any two perfect matchings are related by an automorphism that permutes the vertices in each cluster.

enter image description here

Now I can report on some computations. It turned out to be trickier that expected because of graphs with extremely large groups and matching counts. For the record I'll give the method.

$G$ is a graph with $n$ vertices and automorphism group $\varGamma$. "Matching" means "perfect matching", and "matching-transitive" means "$\varGamma$ acts transitively on the set of all matchings".

$G$ is matching-transitive iff each of its components is matching-transitive, so let's assume $G$ is connected.

Let $P_1,\ldots,P_k$ be the orbits of the action of $\varGamma$ on the pairs of edges of $G$. The "profile" of a matching $M$ is the list $m_1,\ldots,m_k$ where for each $j$ exactly $m_j$ of the $\binom{n/2}{2}$ pairs of edges of $M$ lie in $P_j$. Clearly, every matching in a matching-transitive graph has the same profile (but the converse might not be true).

  1. Compute $\varGamma$.
  2. Start a scan of all matchings, halting when any of these conditions become true: (A) two different profiles have been seen; (B) the number of matchings exceeds $|\varGamma|$; (C) the number of matchings exceeds some huge number chosen to prevent memory overflow; (D) the search completes without (A)-(C) happening.
  3. In the case of (A) or (B), $G$ is not matching-transitive.
  4. In the case of (C), we failed; think of something else to do.
  5. In the case of (D), apply $\varGamma$ to the list of all matchings to test if they are all equivalent.

Case (C) can happen with a matching-transitive graph having a huge number of matchings. I excluded known examples: complete graphs, complete bipartite graphs, $C_s[\bar K_t]$, where $s$ is odd and $t$ is even (defined above). With those cases out of the picture, I have not encountered case (C).

In the case of vertex-transitive graphs, the only examples I found were:

  • complete graphs, balanced complete bipartite graphs, $C_s[\bar K_t]$, where $s$ is odd and $t$ is even
  • Petersen graph, Coxeter graph, Heawood graph

These tests did not require that every edge is contained in some matching, but that is true for all the examples. The graphs tested were:

  • All transitive graphs to 46 vertices
  • All cubic transitive graphs to 1280 vertices
  • All quartic symmetric (arc-transitive) graphs up to 640 vertices

The problem for large graphs is that the my crude backtrack for listing all the matchings starts to take too long. However, all the large cubic or quartic graphs except $C_s[\bar K_2]$ could be eliminated by a different method: use a heuristic to find a hamiltonian cycle and check whether the two (or three, for cubic graphs) matchings implied by the cycle are equivalent. Sometimes this required testing multiple hamiltonian cycles.

For connected regular graphs that are not vertex-transitive, there are too many trivial cases with very few matchings, so I added the criterion that every edge must be contained in a matching. For connected non-transitive cubic graphs, here are the counts starting at $n=6$: 0, 1, 1, 2, 3, 4, 8, 8, 14, 24. For connected non-transitive quartic graphs, the counts starting at $n=8$ are: 0, 1, 2, 6, 5. I didn't attempt to make any sense out of them.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Since you bring up the topic of vertex-transitivity: what do the data say about whether 'every edge contained in perfect matching, and matching transitive' implies 'vertex-transitive'? While believable, it does not seem at all clear to me how to try to prove this. Given two vertices $x$ and $y$, one can of course usually choose two distinct perfect matchings containing them, but there is no 'local' reason why the assumption of matching-transitivity should imply that there is an automorphism interchanging the $x$ and $y$. Can your program be used to test this implication for some small graphs? $\endgroup$
    – Peter Heinig
    Commented Mar 19, 2018 at 14:35
  • 3
    $\begingroup$ @PeterHeinig : Here is an example with 3 orbits on vertices that you will like. Take disjoint $K_{2,3}$ and $K_3$, then make it cubic by adding 3 edges from the $K_3$ to the larger side of the $K_{2,3}$. It is regular, covered by perfect matchings, matching-transitive, but not vertex-transitive. Now I agree with you that we are unlikely to find all regular examples, but there is still hope of finding all vertex-transitive examples. $\endgroup$
    – Brendan McKay
    Commented Mar 19, 2018 at 23:24
  • $\begingroup$ Thank you for your efforts! Interesting that so far, as far as vertex-transitive graphs, there are only the three very small "sporadic" ones already mentioned (Petersen, Coxeter, Heawood). What about testing some other cage graphs which are not vertex-transitive, like the McGeeGraph - quite small Aut(G), but maybe it is matching-transitive? $\endgroup$
    – Wolfgang
    Commented Mar 21, 2018 at 9:59
1
$\begingroup$

The following answers the question of Katja Berčič at in the comment at 2018-03-16 16:48:59Z: "is there a non $K_{2n}$, non $K_{n,n}$ example of a matching transitive graph of degree at least 3?"

Proposition. The Petersen graph is matching-transitive. This is an example of a non-$K_{2n}$, non-$K_{n,n}$ graph with vertex-degree $\geq 3$ which is matching-transitive.

In more detail, the Petersen graph has precisely six perfect matchings, and the natural permutation action of the automorphism-group of the Petersen graph on the set of perfect matchings is transitive, the stabilizer of each perfect matching has cardinality $20$, hence in particular for any two perfect matchings there are precisely $20$ automorphisms taking one to the other.

Proof. It is known and easy to prove that the only perfect matchings of the Petersen graph are the six perfect matchings represented by

enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here

Since the last five perfect matchings displayed above are obviously in one and the same orbit of the (action induced by) the automorphism group, it suffices to show that there is an automorphism mapping the second to the first. Such an automorphism is given by the numbered blue circles in the following two pictures:

enter image description here

enter image description here

This proves transitivity. (By the way, the transitivity is also mentioned, without proof, in Exercise 4.7.6 of [Chris Godsil, Gordon Royle, Algebraic Graph Theory, Springer 2001]). Moreover, by page 65, 2. paragraph of op. cit., the automorphism group of the Petersen graph is $A=\mathrm{Sym}(5)$. Further, by elementary group-theory, for any transitive group-action, all stabilizers have the same cardinality $\frac{\lvert A\rvert}{\lvert\text{set of all perfect matchings}\rvert}=120/6=20$. By basic group-theory, the set of automorphisms taking one matching to another is a coset of a stabilizer, hence has the same cardinality. This completes the proof of the proposition.

Improve this answer
$\endgroup$
4
  • $\begingroup$ For the Petersen graph, you can check that very quickly using the $5\choose2$-subsets as vertices. :-) $\endgroup$
    – Wolfgang
    Commented Mar 17, 2018 at 21:40
  • 1
    $\begingroup$ That's a good example. The OP already gave another example, though confusingly OP doesn't say so explicitly: the Coxeter graph. A proof of its 1-factor-transitivity is here: famnit.upr.si/files/files/seminarji/… I think that OP is also claiming the Heawood graph as an example. $\endgroup$
    – Brendan McKay
    Commented Mar 18, 2018 at 0:54
  • $\begingroup$ @Wolfgang: thanks, you are right: the Petersen graph is the Johnson graph $J(5,2,0)$, which often helps. I knew that once but had forgotten it. $\endgroup$
    – Peter Heinig
    Commented Mar 18, 2018 at 8:33
  • 1
    $\begingroup$ @BrendanMcKay No need to feel confused, it's all in the sentence just before my last edit! $\endgroup$
    – Wolfgang
    Commented Mar 18, 2018 at 9:13

You must log in to answer this question.

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