Number of weak components in powers of imprimitive digraphs

Question

Given any strongly connected digraph $G$ and any $n\in\mathbb{N}$ if we let $d(G)$ be the greatest common factor of the lengths of all the directed cycles in $G$ then does the $n^{\text{th}}$ power digraph $G^n$ always have exactly $\gcd(n,d(G))$ weakly connected components?

Where $G^n=(V(G),E(G)^n)$ with $E(G)^n=\underbrace{E(G)\circ \cdots \circ E(G)}_{n\text{ times}}$ via relation composition.

I mean clearly $G^n$ can have at most $\gcd(n,d(G))$ weakly connected components since there is a partition $\{V_1,V_2,\ldots V_{d(G)}\}$ of $V(G)$ for which $E(G)\subseteq V_{d(G)}\times V_1\cup\bigcup_{k=1}^{d(G)-1}V_k\times V_{k+1}$.

Answer 1

Yes, the number of components of $G^n$ is always $k = \gcd(n, d(G))$, and in fact they are not just weakly but strongly connected components.

First, here are some results about the existence of walks in $G$ relative to the partition $\{V_1,V_2,\ldots V_{d(G)}\}$.

Lemma 1. For any vertex $v$ and any sufficiently large length $\ell$ divisible by $d(G)$, there is a closed walk of length $\ell$ containing $v$.

Proof. Let $C_1, C_2, \dots, C_m$ be some cycles in $G$, with $C_i$ of length $\ell_i$, such that $d(G) = \gcd(\ell_1, \ell_2, \dots, \ell_m)$. We begin by choosing a vertex $v_i \in C_i$ for each $i$, and finding a walk that goes from $v$ to $v_1$ to $v_2$ and so on to $v_m$, then back to $v$.

This closed walk must have a length divisible by $d(G)$. We can modify its length by adding any of $\ell_1, \dots, \ell_m$ to it any number of times, by inserting one of $C_1, \dots, C_m$ into the walk. Since all sufficiently large multiples of $d(G)$ are sums of $\ell_1, \dots, \ell_m$, all sufficiently large multiples of $d(G)$ can be lengths of a closed walk containing $v$.

Lemma 2. For any vertices $x \in V_i$, $y \in V_j$ and any sufficiently large length $\ell$ such that $\ell \equiv j-i \pmod {d(G)}$, there is an $x,y$-walk of length $\ell$ in $G$.

Begin by finding any $x,y$-path in $G$. Since all edges in $G$ go from one part among $\{V_1, \dots, V_{d(G)}\}$ to the next part, the length of this $x,y$-path is congruent to $j-i$ modulo $d(G)$ as desired. We can follow it up by a closed walk containing $y$ whose length is any sufficiently large multiple of $d(G)$ (by the first lemma).

---

We know ahead of time what the $k$ components of $G^n$ ought to be. They are:

• $W_1 = V_1 \cup V_{k+1} \cup \dots \cup V_{d(G)-k+1}$,
• $W_2 = V_2 \cup V_{k+2} \cup \dots \cup V_{d(G)-k+2}$,
• ...,
• $W_k = V_k \cup V_{2k} \cup \dots \cup V_{d(G)}$.

We can certainly prove that there are no edges between these parts in $G^n$; the hard part is showing that they're strongly connected.

Let $x \in V_i$ and $y \in V_j$ be in the same supposedly-component $W_{i \bmod k}$. By the second lemma, we have an $x,y$-walk of any sufficiently large length $\ell$ satisfying $\ell \equiv j-i \pmod {d(G)}$. By Bezout's lemma, we can find constants $A,B \in \mathbb Z$ such that $Ad(G) + Bn = k$, so that $k - Ad(G)$ is a multiple of $n$. Multiplying by $\frac{j-i}{k}$, we see that $(j-i) - A'd(G)$ is a multiple of $n$. Therefore so are each of $(j-i) + (n - A')d(G)$, $(j-i) + (2n-A')d(G)$,and so forth.

One of these is sufficiently large for there to be an $x,y$-walk of that length. Therefore there is an $x,y$-walk of length divisible by $n$, and by taking every $n^{\text{th}}$ vertex in that walk, we get an $x,y$-walk in $G^n$.

Since this can be done for any $x,y$ in the same part of the partition $\{W_1,W_2, \dots, W_k\}$, we conclude that $G^n[W_1], \dots, G^n[W_k]$ are strongly connected.