# On homomorphisms between vertex transitive graphs

In general there is no relation between automorphism groups of subgraphs and the main graph. However, this question is about vertex transitive graphs.

Given vertex transitive $G$ and $H$ such that $|\mathcal{V}(G)|<|\mathcal{V}(H)|$.

If $\mathcal{Aut}(G)\supset\mathcal{Aut}(H)$, is $G\leq H$?

If $G\leq H$, is $\mathcal{Aut}(G)\supset\mathcal{Aut}(H)$?

(I suspect the answer to the second question is no.)

Given vertex transitive $G$ and $H$ such that $|\mathcal{V}(G)|>|\mathcal{V}(H)|$.

If $\mathcal{Aut}(G)\supset\mathcal{Aut}(H)$, is $G\rightarrow H$?

If $G\rightarrow H$, is $\mathcal{Aut}(G)\supset\mathcal{Aut}(H)$?

(Again I suspect the answer to the second question is no.)

$\rightarrow$ implies homomorphism exists in the direction suggested.

## 1 Answer

The answer to the first question is certainly no. The automorphism group of the Petersen graph $H$ is $\mathfrak S_5$ so is equal to the automorphism group of the complete graph $G=K_5$, which has strictly fewer vertices. Both these graphs are vertex transitive and yet the Petersen graph has no $5$-clique, so $G$ is not a subgraph of $H$.

The second question is very strange. I must misunderstand, otherwise the isolated vertex in a non-trivial vertex transitive graph (say a 3-cycle for concreteness) is an immediate counterexample.

The third question also immediately admits a negative answer: take $G$ equal to the Petersen graph again and $H$ equal to 5 isolated vertices.

I don't know about the fourth question, though one can reduce to $H$ being a (connected) core.

• I think the answer for all are no. Thankyou for the examples. – Brout Oct 22 '13 at 22:51