Automorphism group action leads to a "quotient graph"

Question

Let $G$ be a simple (finite) graph. Consider the next natural equivalence relation $\sim$ on $V(G)$:

$u\sim v$ iff there exists and automorphism $\phi\in Aut(G)$, such that $\phi(u)=v$.

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

Note, that if $G$ has trivial automorphism group, then $G_{Aut}\simeq G$. Similarly, if $G$ is vertex-transitive, then $G_{Aut}\simeq K_{1}$.

I have two questions

$\cdot$ Does for every $G$ there exists $H$ such that $H_{Aut}\simeq G\ ?$ (I think the answer is YES)

$\cdot$ If so, how many vertices $H$ must have?

Answer 1

I also think that the answer to the first question is yes. Your note shows us that it is enough to consider graphs with non trivial automorphism group. If we can transform them in such a way, that we destroy all the initial (old) automorphisms, without creating vertices that can not be reached by new automorphisms. We are done. I think it can be done this way:

Consider the transformation which takes the $n$-dimensional hypercube to the $n+1$ dimensional one. (Or you can call it Cartesian product with $K_2$) We will do something similar. Take an exact copy of the initial graph $G$, and connect one vertex from each nontrivial orbit to its counterpart. In the resulting graph there will be no old automorphisms which can move them, since they can be moved only to each other, but they are from different orbits. We also did not create unreachable vertices since we can take every vertex to its counterpart and vice versa.

Iterating this procedure we can eliminate every old automorphism, but the number of vertices of the resulting graph grows exponentially with the number of transformations.

EDIT: If we take $n+1$ copies of $G$, and from every nontrivial old orbit, we chose a single vertex, and put a clicque on the vertices corresponding to the chosen one in the copies, then it is clear that the chosen vertices must map to each other.

Answer 2

I think the answer to Question 1 is yes, at least for finite graphs.

Lets $(T,E)$ be a graph. You can choose a group $G$ that is large enough to do the following: For each node $x∈V$ choose a subgroup $G_x$ (called stabilizer) such that the intersection of all subgroups is $\{1\}$ and each subgroup has a different cardinality. Then you can form the graph in the following way: $$ V= \dot\bigcup_{t∈T} \{gG_t\mid g∈G\}, \mbox{ and } F=\{(gG_s,hG_t)\mid g,h∈G, (s,t)∈E\}.$$

Then each node $t$ is broken up into $|G/G_t|$ pairwise unconnected nodes. And each edge is split up into a complete bipartite graph connecting all equivalent vertices. By changing the group size and the size of the stabilizer you can ensure that any two edges in $F$ have the same valency iff they belong to the same node in $T$.

For more information:

• Monika Zickwolff: Darstellung Symmetrischer Strukturen durch Transversale, In: Contributions to General Algebra 7, Teubner, Wien/Stuttgart
• Daniel Borchmann and Berhard Ganter: Concept Lattice Orbifolds – First Steps, In: Formal Concept Analysis, LNAI 5548, Springer, p. 22

Edit: I forgot to mention that each orbit in $(V,F)$ must be connected in certain cases (e.g. considering the lattice family $M_n$ as graphs). For each node $t∈T$ choose a (connected) Cayley graph $C_t=(G/G_t,E_t)$ and add its edges to $F$ so that the above formula reads $$F=\{(gG_s,hG_t)\mid g,h∈G, (s,t)∈E\}∪⋃_{t∈T}E_t.$$

Addendum: Size estimation.

Assuming the node are numbered by $1,…,n$, one way to assure that each node has different cardinality is to split each node $i$ into the circle $C_{(n+3)k^i}$. So we get an exponential upper bound.

However, in many cases a much smaller size can be achieved as you have to split up only as many nodes as a minimal system of generators of the automorphism group has (split up nodes instead of linking them to copies in Daniels Answer). E.g., for the complete graph $K_n$ the nodes can be replaced by circles of length $4$ to $n+4$ leading to a total size of $\frac{n(n+1)}{2}+3n$ nodes, which is polynomial. This is probably not the lower bound as it should be possible to replace certain circles by smaller Cayley graphs.