Skip to main content
fixed isomorphism (which is between distinct structures) to automorphism
Source Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

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

What if, instead of taking $x$ to $y$ as above, we require the isomorphismautomorphism $\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$).

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

What if, instead of taking $x$ to $y$ as above, we require the isomorphism $\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$).

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$).

Source Link
DRJ
  • 234
  • 2
  • 9

Imposing reciprocity in the definition of vertex-transitivity

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

What if, instead of taking $x$ to $y$ as above, we require the isomorphism $\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$).