An exercise from a book that I am currently studying asks to show the following.

Let $B$ be a block of imprimitivity of $\rm{Aut}(G)$ for a vertex-transitive graph $G.$ Then the graph induced by $B$ is regular.

Am I missing something or is a more stronger claim than this true? Namely, that the induced subgraph is vertex-transitive? For if $u,v \in B$ then there is a $g \in \rm{Aut}(G)$ such that $u^g = v$ and clearly $g \in \rm{Aut}(G[B])$ from the fact that $B$ is a block of imprimitivity. Am I missing something here?

Another question that I would like to consider here is :

What are some nice blocks of imprimitivity for some graphs? Are there any nice applications for them?

The only non-trivial blocks of imprimitivity that I could think of are the antipodal vertices of the odd cycle $C_{2n}$ and Hypercube $Q_n$ and a bipartition of a bipartite vertex-transitive graph.


You are not missing anything, the subgraph induced by a block of imprimitivity is a vertex transitive graph.

Constructing blocks: If $u\in V(G)$ then the set of points fixed by $\mathrm{Aut}(G)_u$ is guaranteed to be a block of imprimitivity. The block in even cycles and in the hypercubes arise in this way. If $N$ is an intransitive normal subgroup of $\mathrm{Aut}(G)$, then its orbits are blocks; for example vertex-transitive bipartite graphs. The centre of the automorphism group will often work, provided it's non-trivial. If $G$ is a Cayley graph for a group $\Gamma$ and $\mathrm{Aut}(G)=\Gamma$, then any non-identity proper subgroup gives a non-trivial block of imprimitivity.

Another way of thinking about this is that systems of imprimitivity are just equivalence relations on $V(G)$ that are invariant under $\mathrm{Aut}(G)$. For examples, a graph of diameter $d$ is antipodal if "equals or is at distance $d$ from" is a nontrivial equivalence relation. Hypercubes are antipodal, as is the line graph of the Petersen graph ($d=3$).

If a distance-transitive graph has a block of imprimitivity, the graph is antipodal or bipartite.


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.