Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

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

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.

share|improve this question
2  
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

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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 Stricker Jul 11 '12 at 19:38
    
I extended my answer. –  Aaron Meyerowitz Jul 12 '12 at 5:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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