4
$\begingroup$

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$

alt text (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$:

alt text (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.

$\endgroup$
2
  • 2
    $\begingroup$ 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\\}$. $\endgroup$
    – Will Sawin
    Jul 11, 2012 at 0:57
  • $\begingroup$ A Cayley graph of $A_5$ would probably provide a less silly example, but I'm not sure what generating set you should use. $\endgroup$
    – Will Sawin
    Jul 11, 2012 at 1:03

1 Answer 1

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$ Jul 11, 2012 at 19:38
  • $\begingroup$ I extended my answer. $\endgroup$ Jul 12, 2012 at 5:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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