Return to Question

###Motivation

For vertex-transitive graphs $G_1, G_2$ the Cartesian product $G_1\square G_2$ is vertex-transitive, too. I am looking for generalized graph products that have the same property, but allow to construct more vertex-transitive graphs than it is possible with the Cartesian product alone.

###Definitions

Cartesian product $G \square H$:

1. $V(G \square H) = V(G) \times V(H)$
2. $(gh)(g'h') \in E(G \square H)$ iff
   • $g = g'$ and $hh' \in E(H)$ or
   • $h = h'$ and $gg' \in E(G)$

Let $G_1, G_2$ be (finite) graphs with vertex sets $V_1, V_2$.

Let $N_1, N_2$ be the normalizers of the resp. automorphism groups, i.e. symmetry preserving permutations.

Let $\pi_1, \pi_2$ be mappings $\pi_1: V_1 \rightarrow N_2$, $\pi_2: V_2 \rightarrow N_1$, i.e. each vertex of one of the graphs is mapped to a symmetry preserving permutation of the other graph. Let $\pi := (\pi_1,\pi_2)$.

Symmetry perserving product $G \square_\pi H$:

1. $V(G \square_\pi H) = V(G) \times V(H)$
2. $(gh)(g'h') \in E(G \square_\pi H)$ iff
   • $g = g'$ and $\pi_1^{-1}(g)(hh') \in E(H)$ or
   • $h = h'$ and $\pi_2^{-1}(h)(gg') \in E(G)$

###Example

For $G = C_5$, $H = K_2$ and

• $\pi_1(i) = \text{id}$ for $i=1,\dots,5$
• $\pi_2(1) = \text{id}$
• $\pi_2(2) = (1)(2354)$

we find, that the Petersen graph is $C_5 \square_\pi K_2$:

^(source)

###Questions

Does the conjecture

$G\square_\pi H$ is vertex-transitive for all vertex-transitive graphs $G,H$ and symmetry preserving mappings $\pi$.

hold?

Assuming that the answer is positive, consider the set $\Gamma$ of constructable vertex-transitive graphs which could be defined inductively:

• $K_n \in \Gamma$
• $C_n \in \Gamma$
• if $G \in \Gamma$ then the complement $\ \overline{G} \in \Gamma$
• if $G,H \in \Gamma$ and $\pi$ is a symmetry preserving mapping, then $\ G\square_\pi H \in \Gamma$

I wonder how the set of constructable vertex-transitive graphs might be characterized, resp. what are necessary and/or sufficient conditions. Or the other way around: which vertex-transitive graphs are not constructable, and how many are there asymptotically?

EDIT: I omitted an intermediate step: Let $\pi_i: V(G_i) \rightarrow \text{Aut}(G_j)$ be an adjacency preserving mapping. I am quite sure that the conjecture

$G\square_\pi H$ is vertex-transitive for all vertex-transitive graphs $G,H$ and adjacency preserving mappings $\pi$.

holds.

Motivation

For vertex-transitive graphs $G_1, G_2$ the Cartesian product $G_1\square G_2$ is vertex-transitive, too. I am looking for generalized graph products that have the same property, but allow to construct more vertex-transitive graphs than it is possible with the Cartesian product alone.

Definitions

Cartesian product $G \square H$:

1. $V(G \square H) = V(G) \times V(H)$
2. $(gh)(g'h') \in E(G \square H)$ iff
   • $g = g'$ and $hh' \in E(H)$ or
   • $h = h'$ and $gg' \in E(G)$

Let $G_1, G_2$ be (finite) graphs with vertex sets $V_1, V_2$.

Let $N_1, N_2$ be the normalizers of the resp. automorphism groups, i.e. symmetry preserving permutations.

Let $\pi_1, \pi_2$ be mappings $\pi_1: V_1 \rightarrow N_2$, $\pi_2: V_2 \rightarrow N_1$, i.e. each vertex of one of the graphs is mapped to a symmetry preserving permutation of the other graph. Let $\pi := (\pi_1,\pi_2)$.

Symmetry perserving product $G \square_\pi H$:

1. $V(G \square_\pi H) = V(G) \times V(H)$
2. $(gh)(g'h') \in E(G \square_\pi H)$ iff
   • $g = g'$ and $\pi_1^{-1}(g)(hh') \in E(H)$ or
   • $h = h'$ and $\pi_2^{-1}(h)(gg') \in E(G)$

Example

For $G = C_5$, $H = K_2$ and

• $\pi_1(i) = \text{id}$ for $i=1,\dots,5$
• $\pi_2(1) = \text{id}$
• $\pi_2(2) = (1)(2354)$

we find, that the Petersen graph is $C_5 \square_\pi K_2$:

^(source)

Questions

Does the conjecture

$G\square_\pi H$ is vertex-transitive for all vertex-transitive graphs $G,H$ and symmetry preserving mappings $\pi$.

hold?

Assuming that the answer is positive, consider the set $\Gamma$ of constructable vertex-transitive graphs which could be defined inductively:

• $K_n \in \Gamma$
• $C_n \in \Gamma$
• if $G \in \Gamma$ then the complement $\ \overline{G} \in \Gamma$
• if $G,H \in \Gamma$ and $\pi$ is a symmetry preserving mapping, then $\ G\square_\pi H \in \Gamma$

I wonder how the set of constructable vertex-transitive graphs might be characterized, resp. what are necessary and/or sufficient conditions. Or the other way around: which vertex-transitive graphs are not constructable, and how many are there asymptotically?

EDIT: I omitted an intermediate step: Let $\pi_i: V(G_i) \rightarrow \text{Aut}(G_j)$ be an adjacency preserving mapping. I am quite sure that the conjecture

$G\square_\pi H$ is vertex-transitive for all vertex-transitive graphs $G,H$ and adjacency preserving mappings $\pi$.

holds.

###Motivation

For vertex-transitive graphs $G_1, G_2$ the Cartesian product $G_1\square G_2$ is vertex-transitive, too. I am looking for generalized graph products that have the same property, but allow to construct more vertex-transitive graphs than it is possible with the Cartesian product alone.

###Definitions

Cartesian product $G \square H$:

1. $V(G \square H) = V(G) \times V(H)$
2. $(gh)(g'h') \in E(G \square H)$ iff
   • $g = g'$ and $hh' \in E(H)$ or
   • $h = h'$ and $gg' \in E(G)$

Let $G_1, G_2$ be (finite) graphs with vertex sets $V_1, V_2$.

Let $N_1, N_2$ be the normalizers of the resp. automorphism groups, i.e. symmetry preserving permutations.

Let $\pi_1, \pi_2$ be mappings $\pi_1: V_1 \rightarrow N_2$, $\pi_2: V_2 \rightarrow N_1$, i.e. each vertex of one of the graphs is mapped to a symmetry preserving permutation of the other graph. Let $\pi := (\pi_1,\pi_2)$.

Symmetry perserving product $G \square_\pi H$:

1. $V(G \square_\pi H) = V(G) \times V(H)$
2. $(gh)(g'h') \in E(G \square_\pi H)$ iff
   • $g = g'$ and $\pi_1^{-1}(g)(hh') \in E(H)$ or
   • $h = h'$ and $\pi_2^{-1}(h)(gg') \in E(G)$

###Example

For $G = C_5$, $H = K_2$ and

• $\pi_1(i) = \text{id}$ for $i=1,\dots,5$
• $\pi_2(1) = \text{id}$
• $\pi_2(2) = (1)(2354)$

we find, that the Petersen graph is $C_5 \square_\pi K_2$:

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

###Questions

Does the conjecture

$G\square_\pi H$ is vertex-transitive for all vertex-transitive graphs $G,H$ and symmetry preserving mappings $\pi$.

hold?

Assuming that the answer is positive, consider the set $\Gamma$ of constructable vertex-transitive graphs which could be defined inductively:

• $K_n \in \Gamma$
• $C_n \in \Gamma$
• if $G \in \Gamma$ then the complement $\ \overline{G} \in \Gamma$
• if $G,H \in \Gamma$ and $\pi$ is a symmetry preserving mapping, then $\ G\square_\pi H \in \Gamma$

I wonder how the set of constructable vertex-transitive graphs might be characterized, resp. what are necessary and/or sufficient conditions. Or the other way around: which vertex-transitive graphs are not constructable, and how many are there asymptotically?

EDIT: I omitted an intermediate step: Let $\pi_i: V(G_i) \rightarrow \text{Aut}(G_j)$ be an adjacency preserving mapping. I am quite sure that the conjecture

$G\square_\pi H$ is vertex-transitive for all vertex-transitive graphs $G,H$ and adjacency preserving mappings $\pi$.

holds.

###Motivation

For vertex-transitive graphs $G_1, G_2$ the Cartesian product $G_1\square G_2$ is vertex-transitive, too. I am looking for generalized graph products that have the same property, but allow to construct more vertex-transitive graphs than it is possible with the Cartesian product alone.

###Definitions

Cartesian product $G \square H$:

1. $V(G \square H) = V(G) \times V(H)$
2. $(gh)(g'h') \in E(G \square H)$ iff
   • $g = g'$ and $hh' \in E(H)$ or
   • $h = h'$ and $gg' \in E(G)$

Let $G_1, G_2$ be (finite) graphs with vertex sets $V_1, V_2$.

Let $N_1, N_2$ be the normalizers of the resp. automorphism groups, i.e. symmetry preserving permutations.

Let $\pi_1, \pi_2$ be mappings $\pi_1: V_1 \rightarrow N_2$, $\pi_2: V_2 \rightarrow N_1$, i.e. each vertex of one of the graphs is mapped to a symmetry preserving permutation of the other graph. Let $\pi := (\pi_1,\pi_2)$.

Symmetry perserving product $G \square_\pi H$:

1. $V(G \square_\pi H) = V(G) \times V(H)$
2. $(gh)(g'h') \in E(G \square_\pi H)$ iff
   • $g = g'$ and $\pi_1^{-1}(g)(hh') \in E(H)$ or
   • $h = h'$ and $\pi_2^{-1}(h)(gg') \in E(G)$

###Example

For $G = C_5$, $H = K_2$ and

• $\pi_1(i) = \text{id}$ for $i=1,\dots,5$
• $\pi_2(1) = \text{id}$
• $\pi_2(2) = (1)(2354)$

we find, that the Petersen graph is $C_5 \square_\pi K_2$:

^(source)

###Questions

Does the conjecture

$G\square_\pi H$ is vertex-transitive for all vertex-transitive graphs $G,H$ and symmetry preserving mappings $\pi$.

hold?

Assuming that the answer is positive, consider the set $\Gamma$ of constructable vertex-transitive graphs which could be defined inductively:

• $K_n \in \Gamma$
• $C_n \in \Gamma$
• if $G \in \Gamma$ then the complement $\ \overline{G} \in \Gamma$
• if $G,H \in \Gamma$ and $\pi$ is a symmetry preserving mapping, then $\ G\square_\pi H \in \Gamma$

I wonder how the set of constructable vertex-transitive graphs might be characterized, resp. what are necessary and/or sufficient conditions. Or the other way around: which vertex-transitive graphs are not constructable, and how many are there asymptotically?

EDIT: I omitted an intermediate step: Let $\pi_i: V(G_i) \rightarrow \text{Aut}(G_j)$ be an adjacency preserving mapping. I am quite sure that the conjecture

$G\square_\pi H$ is vertex-transitive for all vertex-transitive graphs $G,H$ and adjacency preserving mappings $\pi$.

holds.

###Motivation

For vertex-transitive graphs $G_1, G_2$ the Cartesian product $G_1\square G_2$ is vertex-transitive, too. I am looking for generalized graph products that have the same property, but allow to construct more vertex-transitive graphs than it is possible with the Cartesian product alone.

###Definitions

Cartesian product $G \square H$:

1. $V(G \square H) = V(G) \times V(H)$
2. $(gh)(g'h') \in E(G \square H)$ iff
   • $g = g'$ and $hh' \in E(H)$ or
   • $h = h'$ and $gg' \in E(G)$

Let $G_1, G_2$ be (finite) graphs with vertex sets $V_1, V_2$.

Let $N_1, N_2$ be the normalizers of the resp. automorphism groups, i.e. symmetry preserving permutations.

Let $\pi_1, \pi_2$ be mappings $\pi_1: V_1 \rightarrow N_2$, $\pi_2: V_2 \rightarrow N_1$, i.e. each vertex of one of the graphs is mapped to a symmetry preserving permutation of the other graph. Let $\pi := (\pi_1,\pi_2)$.

Symmetry perserving product $G \square_\pi H$:

1. $V(G \square_\pi H) = V(G) \times V(H)$
2. $(gh)(g'h') \in E(G \square_\pi H)$ iff
   • $g = g'$ and $\pi_1^{-1}(g)(hh') \in E(H)$ or
   • $h = h'$ and $\pi_2^{-1}(h)(gg') \in E(G)$

###Example

For $G = C_5$, $H = K_2$ and

• $\pi_1(i) = \text{id}$ for $i=1,\dots,5$
• $\pi_2(1) = \text{id}$
• $\pi_2(2) = (1)(2354)$

we find, that the Petersen graph is $C_5 \square_\pi K_2$:

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

###Questions

Does the conjecture

$G\square_\pi H$ is vertex-transitive for all vertex-transitive graphs $G,H$ and symmetry preserving mappings $\pi$.

hold?

Assuming that the answer is positive, consider the set $\Gamma$ of constructable vertex-transitive graphs which could be defined inductively:

• $K_n \in \Gamma$
• $C_n \in \Gamma$
• if $G \in \Gamma$ then the complement $\ \overline{G} \in \Gamma$
• if $G,H \in \Gamma$ and $\pi$ is a symmetry preserving mapping, then $\ G\square_\pi H \in \Gamma$

I wonder how the set of constructable vertex-transitive graphs might be characterized, resp. what are necessary and/or sufficient conditions. Or the other way around: which vertex-transitive graphs are not constructable, and how many are there asymptotically?

EDIT: I omitted an intermediate step: Let $\pi_i: V(G_i) \rightarrow \text{Aut}(G_j)$ be an adjacency preserving mapping. I am quite sure that the conjecture

$G\square_\pi H$ is vertex-transitive for all vertex-transitive graphs $G,H$ and adjacency preserving mappings $\pi$.

holds.

###Motivation

For vertex-transitive graphs $G_1, G_2$ the Cartesian product $G_1\square G_2$ is vertex-transitive, too. I am looking for generalized graph products that have the same property, but allow to construct more vertex-transitive graphs than it is possible with the Cartesian product alone.

###Definitions

Cartesian product $G \square H$:

1. $V(G \square H) = V(G) \times V(H)$
2. $(gh)(g'h') \in E(G \square H)$ iff
   • $g = g'$ and $hh' \in E(H)$ or
   • $h = h'$ and $gg' \in E(G)$

Let $G_1, G_2$ be (finite) graphs with vertex sets $V_1, V_2$.

Let $N_1, N_2$ be the normalizers of the resp. automorphism groups, i.e. symmetry preserving permutations.

Let $\pi_1, \pi_2$ be mappings $\pi_1: V_1 \rightarrow N_2$, $\pi_2: V_2 \rightarrow N_1$, i.e. each vertex of one of the graphs is mapped to a symmetry preserving permutation of the other graph. Let $\pi := (\pi_1,\pi_2)$.

Symmetry perserving product $G \square_\pi H$:

1. $V(G \square_\pi H) = V(G) \times V(H)$
2. $(gh)(g'h') \in E(G \square_\pi H)$ iff
   • $g = g'$ and $\pi_1^{-1}(g)(hh') \in E(H)$ or
   • $h = h'$ and $\pi_2^{-1}(h)(gg') \in E(G)$

###Example

For $G = C_5$, $H = K_2$ and

• $\pi_1(i) = \text{id}$ for $i=1,\dots,5$
• $\pi_2(1) = \text{id}$
• $\pi_2(2) = (1)(2354)$

we find, that the Petersen graph is $C_5 \square_\pi K_2$:

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

###Questions

Does the conjecture

$G\square_\pi H$ is vertex-transitive for all vertex-transitive graphs $G,H$ and symmetry preserving mappings $\pi$.

hold?

Assuming that the answer is positive, consider the set $\Gamma$ of constructable vertex-transitive graphs which could be defined inductively:

• $K_n \in \Gamma$
• $C_n \in \Gamma$
• if $G \in \Gamma$ then the complement $\ \overline{G} \in \Gamma$
• if $G,H \in \Gamma$ and $\pi$ is a symmetry preserving mapping, then $\ G\square_\pi H \in \Gamma$

I wonder how the set of constructable vertex-transitive graphs might be characterized, resp. what are necessary and/or sufficient conditions. Or the other way around: which vertex-transitive graphs are not constructable, and how many are there asymptotically?

EDIT: I omitted an intermediate step: Let $\pi_i: V(G_i) \rightarrow \text{Aut}(G_j)$ be an adjacency preserving mapping. I am quite sure that the conjecture

$G\square_\pi H$ is vertex-transitive for all vertex-transitive graphs $G,H$ and adjacency preserving mappings $\pi$.

holds.