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?

Improve this question
$\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
    Commented 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
    Commented 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: [email protected]. $\endgroup$
    – Sergiy Kozerenko
    Commented Oct 15, 2015 at 9:57

2 Answers 2

Reset to default
10
$\begingroup$

No. Here is a simple counterexample:

enter image description here

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .