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
    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
    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
    Jul 29, 2015 at 22:27
  • $\begingroup$ "For the last claim...." But no claims are made. What do you mean? $\endgroup$
    – Gerry Myerson
    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
    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
    Jul 31, 2015 at 13:54
  • $\begingroup$ Most of the examples are not Cayley - check them out. $\endgroup$
    – Igor Rivin
    Jul 31, 2015 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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