Generalized graph products in view of vertex-transitive graphs

Question

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.

Answer 1

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.)