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$

1 Answer 1

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$
1
  • $\begingroup$ I think the answer for all are no. Thankyou for the examples. $\endgroup$
    – Turbo
    Commented Oct 22, 2013 at 22:51

You must log in to answer this question.

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