Return to 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$

alt text http://epublius.de/mathoverflow/vt1.png

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 http://epublius.de/mathoverflow/vt2.png

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.

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.

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 http://epublius.de/mathoverflow/vt1.png

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 http://epublius.de/mathoverflow/vt2.png

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.

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 http://epublius.de/mathoverflow/vt1.png

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 http://epublius.de/mathoverflow/vt2.png

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.

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 http://epublius.de/mathoverflow/vt1.png

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 http://epublius.de/mathoverflow/vt2.png

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.

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 http://epublius.de/mathoverflow/vt1.png

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 http://epublius.de/mathoverflow/vt2.png

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.