5
$\begingroup$

A graph is vertex transitive if $x \mapsto y$ by an automorphism.

A graph is generously vertex transitive if $x \mapsto y \mapsto x$ by an automorphism.

Simple facts:

  • GVT $\rightarrow$ unimodular. Just plug in the definition of unimodular to see why.

  • Cayley $\not \rightarrow$ GVT. Free product $\mathbb Z_2 * \mathbb Z_3$ is an example.

  • GVT $\not \rightarrow$ Cayley. Petersen graph is a finite example.

Question: Is there an infinite generously vertex transitive connected graph with finite degree which is not a Cayley graph?

(Before edition, it was also asked: "Is there a common name for this property?", answered by Chris Godsil in the comments.)

Thanks!

Improve this question
$\endgroup$
9
  • $\begingroup$ Do you assume your graph to be connected? Otherwise, to answer your first question, you could take infinitely many copies of the Petersen graph. $\endgroup$
    – Erik Rijcken
    Commented Jul 29, 2015 at 13:49
  • 1
    $\begingroup$ Perhaps you want to assume the graph has finite valence? Otherwise, the first question is answered by the complement of @ErikRijcken's example. $\endgroup$
    – Dave Witte Morris
    Commented Jul 29, 2015 at 18:39
  • 4
    $\begingroup$ A permutation group $G$ on a set $V$ is generously transitive if, for each pair of points from $F$, there is an element of $G$ that swaps them. The literature I am aware of focusses on the finite case. $\endgroup$
    – Chris Godsil
    Commented Jul 29, 2015 at 22:27
  • $\begingroup$ "For the last claim...." But no claims are made. What do you mean? $\endgroup$
    – Gerry Myerson
    Commented Jul 30, 2015 at 1:39
  • 1
    $\begingroup$ Thank you all for feedback. Question has been edited to remove some of these obscurities. $\endgroup$
    – user334639
    Commented Jul 31, 2015 at 3:33

2 Answers 2

Reset to default
5
$\begingroup$

Take the graph product $G = P \times \mathbb{Z}$ of the Petersen graph with the infinite path graph. This is clearly infinite, finite-degree, and generously vertex-transitive.

Then we have two distinguishable types of edge, namely $P$-edges (ones which belong to $5$-cycles) and $\mathbb{Z}$-edges (ones which do not). This means that the automorphisms of $G$ must preserve the obvious product structure, and can uniquely be written as compositions of automorphisms of $P$ with automorphisms of $\mathbb{Z}$.

If $G$ were a Cayley graph of some group $H$, then there are three generators corresponding to $P$-edges and two corresponding to $\mathbb{Z}$-edges. The actions of the $P$-generators and $\mathbb{Z}$-generators must, respectively, preserve the $\mathbb{Z}$-coordinate and $P$-coordinate of each vertex.

Hence the $P$-generators and $\mathbb{Z}$-generators each generate disjoint normal subgroups of $H$ (and $H$ is their internal direct product). The normal subgroup generated by the $P$-generators is sharply vertex-transitive on $P$, implying that the Petersen graph is a Cayley graph.

Contradiction.

So $G$ has all the properties you requested.

Improve this answer
$\endgroup$
3
$\begingroup$

It seems that any distance-transitive graph satisfies your condition (of course, distance-transitivity is much stronger), and you can find many examples (both finite and infinite) in Peter Cameron's nice paper. (A census of infinite distance-transitive graphs, Discrete Math, 1998) Many of these are not Cayley graphs, it would appear.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! Were you able to find a specific example there? $\endgroup$
    – user334639
    Commented Jul 31, 2015 at 13:54
  • $\begingroup$ Most of the examples are not Cayley - check them out. $\endgroup$
    – Igor Rivin
    Commented Jul 31, 2015 at 15:53

You must log in to answer this question.

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