8
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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]. $\endgroup$
    – M. Vinay
    Oct 8, 2015 at 8:46
  • $\begingroup$ 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. $\endgroup$
    – M. Vinay
    Oct 8, 2015 at 9:04
  • $\begingroup$ I think you should post your proof as an answer to this question, or you can also mail me at: kozerenkosergiy@ukr.net. $\endgroup$ Oct 15, 2015 at 9:57

2 Answers 2

10
$\begingroup$

No. Here is a simple counterexample:

enter image description here

$\endgroup$
0
3
$\begingroup$

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 @}
    ]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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