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

Consider the simple undirected graph $G$ with natural equivalence relation $\sim$ on $V(G)$:

$u\sim v$ iff they are similar, i.e. iff there exists $\phi\in Aut(G)$ with $\phi(u)=v$.

Define a "quotient graph" $G_{Aut}$ in the following way:

$V(G_{Aut})=V(G)/\sim$ and there is an edge $A-B$ iff $\exists \ a\in A, b\in B$ with $ab\in E(G)$.

Conjecture: If in $G$ every pair of similar vertices are non-adjacent, then $G_{Aut}\subset G \ ?$

ADDED: As Anton showed, this conjecture is false. But what one can said if $G$ is a tree? Does conjecture remains false?

share|improve this question

2 Answers 2

up vote 8 down vote accepted

No. Here is a simple counterexample:

enter image description here

share|improve this answer

The following seems to be a counterexample, verified by a Magma calcualtion. The vertex set is $\{1,2,\ldots,16\}$ and the edge set is $E$. The quotient graph is the complete graph on four vertices and has $S_4$ as automorphism group, but $|{\rm Aut}(G)|=4$.

> E:={
      {1,5}, {2,6}, {3,7},{4,8},

      {1,9}, {1,10}, {1,11}, {1,12},
      {2,9}, {2,10}, {2,11}, {2,12},
      {3,9}, {3,10}, {3,11}, {3,12},
      {4,9}, {4,10}, {4,11}, {4,12},

      {1,14}, {1,15}, {1,16},
      {2,13}, {2,15}, {2,16},
      {3,13}, {3,14}, {3,16},
      {4,13}, {4,14}, {4,15},

      {5,9}, {5,10}, {6,10}, {6,11}, {7,11}, {7,12}, {8,12}, {8,9},

      {5,13}, {5,14}, {6,14}, {6,15}, {7,15}, {7,16}, {8,16}, {8,13},

      {9,13}, {10,14}, {11,15}, {12,16} };

  > G:=Graph<16|E>;
  > A:=AutomorphismGroup(G);
  > Order(A);
    4
  > Orbits(A);
    [
      GSet{@ 1, 2, 3, 4 @},
      GSet{@ 5, 6, 7, 8 @},
      GSet{@ 9, 10, 11, 12 @},
      GSet{@ 13, 14, 15, 16 @}
    ]
share|improve this answer

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.