1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

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

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.