0
$\begingroup$

Say we have a (simple) graph $\Gamma$, and G=Aut($\Gamma$) .

Is it true (in general) that 2 induced subgraphs of $\Gamma$, say $\Gamma_1$ and $\Gamma_2$, are isomorphic iff they are in the same orbit of the action of G?

I suspect that the answer is 'no'.

First, I think one side is true and is trivial: If they are in the same orbit then there is an automorphism that, restricted to the vertices of $\Gamma_1$ and $\Gamma_2$ is an isomorphism.

However, I don't know, that given an isomorphism between $\Gamma_1$ and $\Gamma_2$ if we can extend it to an automorphism on $\Gamma$.

Am I correct so far?

Also, given a graph, how do I go about to show that for this specific graph this argument is true (while not being true in general)? I suspect that it has some connection to the cycle index of the action of G on V.

I know that $Z(G,1+x) = 1+x+2x^2+4x^3+5x^4+5x^5+4x^6+...+x^9$

(the graph in question is $L_2(3)$)

Thanks in advance!

Shay

  • 1
    A vertex or an edge gives you a subgraph. Isn't it obvious that the automorphism group need not act transitively on vertices or edges? It would have to if your statement were true. Maybe I misunderstand the meaning of "induced subgraph", though.2011-07-16

1 Answers 1

1

No. Take two copies $H_1, H_2$ of the same graph $H$ and join them by two vertices $v_1, v_2$, then attach an extremely long path to $v_1$.