1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Such a product (unless it's trivial) must have a degree at most half of the number of vertexes. There are transitive graphs of almost any number of vertexes and degree (odd number of vertexes and odd degree is forbidden): in fact, there's a circulant with any degree (a circulant is a graph with an automorphism that is a cyclic permutation moving all vertices). $\endgroup$ Jul 20, 2012 at 7:30
  • $\begingroup$ Also, the complement of any transitive graph is transitive. The case when one of the factors is $ K_2 $ might thus require special examination, because that's the only way a product can have a degree near half the number of vertexes. $\endgroup$ Jul 20, 2012 at 7:31
  • $\begingroup$ Aaron's example $K_6$ minus a matching has degree 4 which is more than half the number of vertices. Did I misunderstand your argument? $\endgroup$ Jul 20, 2012 at 7:44

2 Answers 2

2
$\begingroup$

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$ ?

alt text

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.

$\endgroup$
8
  • $\begingroup$ Are you sure that your permutation $\pi_2(2)$ is in the normalizer of $\text{Aut}(C_m)$? $\endgroup$ Jul 20, 2012 at 7:08
  • $\begingroup$ $K_6$ minus a matching equals the complement of three copies of $K_2$ and thus is constructable according to my definition. $\endgroup$ Jul 20, 2012 at 7:24
  • $\begingroup$ You are right on both points, I wasn't paying enough attention. My feeling however is simple examples will show problems in all directions. I don't think $C_3 \square_\pi C_m$ would usually be vertex transitive. I might be wrong again. Even $K_2 \square_\pi C_{11}$ seems problematic sometimes. $\endgroup$ Jul 20, 2012 at 7:55
  • 1
    $\begingroup$ @Aaron: By the way: how do you draw such graphs? $\endgroup$ Jul 20, 2012 at 22:42
  • 2
    $\begingroup$ I used Google Sketchup which is a pretty silly way to do it but free and easy to use. $\endgroup$ Jul 21, 2012 at 0:43
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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