Generalized graph products in view of vertex-transitive graphs The Cartesian product of two vertex-transitive graphs is vertex-transitive.
The Petersen graph is vertex-transitive but not the Cartesian product of two vertex-transitive graphs. But almost.
The Cartesian product $G \square H$ of two graphs $G, H$ is defined by:


*

*$V(G \square H) = V(G) \times V(H)$

*$(gh)(g'h') \in E(G \square H)$ iff $g = g'$ and $hh'\in E(H)$ or $h = h'$ and $gg' \in E(G)$


With the topological distance $d: V \times V \rightarrow \lbrace 0, 1, 2\dots\rbrace \cup \lbrace \infty \rbrace$ the second condition reads:


*

*$(gh)(g'h') \in E(G \square H)$ iff $g = g'$ and $d(hh') = 1$ or $h = h'$ and $d(gg') = \mathbf{1}$


Example: $C_5 \square K_2$
 (source)
Consider the following generalization $G \square_f H$ with respect to a labeling $f: V(H) \rightarrow \lbrace 1,2,\dots\rbrace$. (Assume that $G$ is connected and $f(v) \leq \text{diam}(G)$.)


*

*$V(G \square_f H) = V(G) \times V(H)$

*$(gh)(g'h') \in E(G \square_f H)$ iff $g = g'$ and $d(hh') = 1$ or $h = h'$ and $d(gg') = \mathbf{f(h)}$


With $f_P(1) = 1, f_P(2) = 2$ we find, that the Petersen graph is $C_5 \square_{f_P} K_2$:
 (source)
For Cartesian products, i.e. $f(v) \equiv 1 $, it holds:


*

*$G\square H$ is vertex-transitive for all vertex-transitive graphs $G,H$.

*There are non-trivial vertex-transitive graphs $F$ with no vertex-transitive graphs $G,H$ such that $F = G\square H$, e.g. the Petersen graph.


With "trivial" I mean a complete graph, a circle graph, a product of trivial graphs, or the complement of a trivial graph.
I want to ask the following questions:

  
*
  
*Is $G\square_f H$ vertex-transitive for all vertex-transitive graphs $G,H$
  and $H$-labellings $f$?
  
*Is there a non-trivial vertex-transitive graph $F$ with no vertex-transitive graphs
  $G,H$ and $H$-labelling $f$ such that $F = G\square_f H$?

Because arbitrary graphs (almost) always hold a surprise when growing larger I better should ask for the smallest examples of

  
*
  
*two vertex-transitive graphs $G,H$ and a $H$-labelling $f$ such that
  $G\square_f H$ is not
  vertex-transitive
  
*a non-trivial vertex-transitive graph $F$ with no vertex-transitive graphs $G,H$ and
  $H$-labelling $f$ such that $F = 
> G\square_f H$

If - hypothetically - there were no such examples this would imply that every vertex-transitive graph is trivial (in the sense above) or a (generalized) product of two vertex-transitive graphs. This would allow for the construction of all vertex-transitive graphs from a trivial base set.
If there are such examples there are two routes of further investigation: to treat them as exceptional cases (like the trivial ones) or to further or otherwise generalize the definition of a product.
 A: For the second question Will's example is to the point. Another description: start with a $k$-gon ($k \gt 3$ an odd prime) and decide that the obvious cyclic group will act transitively on the final graph. The chosen edges are one of the $\frac{k-1}2$ orbits of possible edges. Chose some more orbits. Since $k$ is prime, no product is possible.
A silly counter example to the first question is to mimic the Peterson-graph construction with a $4$ cycle. With $f_P(1) = 1, f_P(2) = 2$ we find, that  $C_4 \square_{f_P} K_2$ has four vertices of degree $3$ and four of degree $2$.
A regular but non-transitive example is $C_9 \square_{f_P} K_2$ with $f_P(1) = 1, f_P(2) = 3.$ Now all the vertices are degree $3$ but half are in triangles and the other half not.
later I doubt that this would be a helpful construction. It is easy to make a bipartite vertex transitive graph of order $2p$ with $p$ an odd prime. None of these could be a product. A product $A \square_f B$ with $2p$ vertices either has $A=K_2$ , in which case it is a Cartesian product and not bipartite, or $B=K_2$ in which  case it is two non-trivial vertex transitive $p$ vertex graphs joined by a single matching and again could not be bipartite. 
Consider families such as $K_{2m}$ minus a matching or $K_{m,m}$ or $K_{m,m}$ minus a matching. Can you construct all of these or even any of these for $m \gt 5$ (I don't know about $m=3,4,5$ but I imagine there could be a few small cases.)
