MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
    
I commented on your other question too, but I shall ask here just in case. Have you done anything in this topic, or do you intend to do so? I'm hoping to work on it, but if you're doing some serious research in this, I'd prefer to do something different from what you're doing [within the same topic]. – M. Vinay Oct 8 '15 at 8:46
    
And your conjecture is true for trees (I proved it just now). I can post the outline of the proof if you're interested [or email it to you or something]. It's not difficult to prove anyway. – M. Vinay Oct 8 '15 at 9:04
    
I think you should post your proof as an answer to this question, or you can also mail me at: kozerenkosergiy@ukr.net. – Sergiy Kozerenko Oct 15 '15 at 9:57
up vote 9 down vote accepted

No. Here is a simple counterexample:

enter image description here

share|cite|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|cite|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.