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$

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$:

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.