# Automorphism group action leads to a "quotient graph"

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?

• It's been over two years (which is not that long a time in mathematics research, I know), so have you done anything with this yet? I find the idea interesting, but I wouldn't want to tread on your toes. Sep 17, 2015 at 14:44
• I haven't really did anything significant research on this topic. One obviuos idea was to "substitute" each vertex in a graph with some vertex-transitive graph, but then we must keep track of the new possible automorphisms (and this seems hard to do). Oct 15, 2015 at 9:56
• Yes, I thought the same, but didn't pursue it further. I'm actually working on it from the other direction, and not trying to solve the exact problem you posted. I want to use quotienting to measure symmetry of a graph in a different way [as opposed to classifying graphs as vertex-transitive, edge-transitive, etc.]. Oct 15, 2015 at 10:04
• So you interested in $Aut(G_{Aut})$ as a measure symmetry of $G$? Oct 15, 2015 at 10:07
• Sort of. Vertex-transitive graphs are "highly symmetric", because their quotient is always $K_1$. Identity graphs, on the other hand, are "self-quotient". Other graphs are in-between. For example, some graphs might not be asymmetric themselves, but their quotients may be identity graphs (like the example graph given in the other thread). We (there's another person working on this with me) are looking at the sequence of quotient graphs — they may be similar in some ways to sequences and series of groups. Oct 15, 2015 at 14:36

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.

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$.

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.$$
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.