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

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

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.

share|improve this question
    
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). –  Zsbán Ambrus Jul 20 '12 at 7:30
    
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. –  Zsbán Ambrus Jul 20 '12 at 7:31
    
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? –  Hans Stricker Jul 20 '12 at 7:44
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
Are you sure that your permutation $\pi_2(2)$ is in the normalizer of $\text{Aut}(C_m)$? –  Hans Stricker Jul 20 '12 at 7:08
    
$K_6$ minus a matching equals the complement of three copies of $K_2$ and thus is constructable according to my definition. –  Hans Stricker Jul 20 '12 at 7:24
    
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. –  Aaron Meyerowitz Jul 20 '12 at 7:55
    
Could you please give me a hint, how $K_2\square_\pi C_{11}$ could be problematic. –  Hans Stricker Jul 20 '12 at 9:30
    
I am thinking about $C_3\square_\pi C_4 = K_3\square_\pi C_4$ and how it could pose a problem. If this is not the smallest counter-example, maybe $C_3\square_\pi C_5 = K_3\square_\pi C_5$? (Looking for counter-examples is appropriate if one doubts a conjecture. I still believe in it - until I see a counter-example. So I should try to prove the conjecture - that $G\square_\pi H$ is vertex-transitive for vertex-transitive $G,H$.) Nevertheless I'd appreciate any worked-out counter-example! –  Hans Stricker Jul 20 '12 at 14:18
show 3 more comments

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.

share|improve this answer
add comment

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.