Symmetry preserving graph products

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.

Answer 1

Revised answer (see previous version to make sense of comments):

The Petersen graph is a small wonderful and rather exceptional creature. It is not a paradigm.

Does this graph fit your construction with $G = C_7$, $H = K_2$ ?

It is not vertex transitive since each red node is in three $5$-cycles but each green node is only in two.

There are many vertex transitive graphs with a prime number of vertices, none of them is a product. So there are graphs which do not arise in this manner.

Your construction takes two graphs $G_i$ with $v_i$ vertices each of degree $d_i$ and some permutations and creates a new one with $v_1v_2$ vertices each of degree $d_1+d_2.$ This can work out to be a rather low degree (or high if a complement is taken.) Consider the Johnson graph $J(6,2)$ whose $\binom{6}{2}=15$ nodes are the pairs from an $6$ set with two adjacent when they share an element. It has degree $2(6-2)=8.$ If it is to be a product then we need $v_1=3$ and $v_2=5$ which allows for degree at most $2+4=6.$ This also does not allow the product to be the complement a regular graph of degree $7.$ A similar obstacle would arise for many vertex transitive graphs just based on the number of vertices and the degree. Certainly for $J(n,2)$ when $n \ge 6$ makes $\binom{n}2$ odd and probably even when $\binom{n}2$ it is even.

Answer 2

There was a paper I saw some years ago that discussed many possible ways of defining the product of two graphs. I am not sure but I think it was this paper:

Nowakowski, Richard J.(3-DLHS); Rall, Douglas F.(1-FURM) Associative graph products and their independence, domination and coloring numbers. (English summary) Discuss. Math. Graph Theory 16 (1996), no. 1, 53–79.

It might be worth checking out, if you want to look at different products.