2
$\begingroup$

A simple, undirected graph is vertex-transitive if for any pair of vertices $x,y$, there exists an automorphism (adjacency-preserving self-bijection) $\phi$ such that $\phi(x)=y$.

What if, instead of taking $x$ to $y$ as above, we require the automorphism $\phi$ to exchange $x$ and $y$, i.e. $\phi(x)=y$ and $\phi(y)=x$?

  1. Is there a name for this natural refinement of the notion of vertex-transitivity?
  2. What is a simple example of a vertex-transitive graph which does not satisfy this?

Note that any Cayley graph whose generating set is conjugacy-invariant does satisfy this exchange property (take $\phi(u)=xu^{-1}y$).

$\endgroup$
5
  • 4
    $\begingroup$ Generously transitive is the name for this property. $\endgroup$ Commented Feb 27, 2022 at 10:32
  • 4
    $\begingroup$ See math.stackexchange.com/questions/953856/… for discussion of this property. $\endgroup$ Commented Feb 27, 2022 at 10:33
  • $\begingroup$ Thank you so much, Gordon! The name "generously transitive" is not very natural, so I would have had a hard time finding it by myself. I am new to this site, what shall I do to validate/close? $\endgroup$
    – DRJ
    Commented Feb 27, 2022 at 12:58
  • $\begingroup$ @GordonRoyle, since @‍DRJ seems satisfied with your comment, would you post it as an answer so that they can accept it? $\endgroup$
    – LSpice
    Commented Feb 27, 2022 at 21:56
  • $\begingroup$ @DRJ To close the question, you accept the answer that I have now given as an actual answer, rather than a comment. $\endgroup$ Commented Feb 28, 2022 at 1:36

1 Answer 1

2
$\begingroup$

A permutation group $G$ acting on a set $X$ is called generously transitive if for any two elements $x$, $y \in X$ there is a permutation $g \in G$ such that $x^g = y$ and $y^g = x$.

It is fairly easy to find examples of vertex-transitive graphs whose automorphism group is not generously transitive, by searching MathOverflow or math.stackexchange.

For example: https://math.stackexchange.com/questions/953856/automorphism-groups-of-vertex-transitive-graphs

$\endgroup$

You must log in to answer this question.

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