Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.