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$ Feb 27 at 10:32
  • 4
    $\begingroup$ See math.stackexchange.com/questions/953856/… for discussion of this property. $\endgroup$ Feb 27 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
    Feb 27 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
    Feb 27 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$ Feb 28 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.