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$

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.

• If $s$ is any set of numbers closed under negation in $\mathbb F_p$, then the set of numbers in $\mathbb F_p$ with $ab \in E$ iff $a-b \in S$ is a vertex-transitive graph. It is not a product because its order is a prime number. It is not necessarily trivial by your definition, e.g. $p=11$, $S=\\{1,2,9,10\\}$. – Will Sawin Jul 11 '12 at 0:57
• A Cayley graph of $A_5$ would probably provide a less silly example, but I'm not sure what generating set you should use. – Will Sawin Jul 11 '12 at 1:03

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.)
• I obviously should have excluded graphs of prime order. What would you recommend: altering the original question - making your and Will's answers somehow obsolete - or asking a new one: Is there a non-trivial vertex-transitive graph $F$ of non-prime order with no vertex-transitive graphs $G,H$ and $H$-labelling $f$ such that $F = G\square_f H$? – Hans-Peter Stricker Jul 11 '12 at 19:38