On the uniqueness of the factorization of power digraphs modulo $n$

Abstract

For each pair of integers $n={\prod }_{i=1}^r{p}_i^{e_i}$ and $k\ge 2$, a digraph $G(n,k)$ is one with vertex set $\{0,1,\dots ,n-1\}$ and for which there exists a directed edge from $x$ to $y$ if $x^k\equiv y(\mathrm{mod}n)$. Using the Chinese Remainder Theorem, the digraph $G(n,k)$ can be written as a direct product of digraphs $G(p_i^{e_i},k)$ for all $i$ such that $1\le i\le r$. A fundamental constituent $G_P^{\ast }(n,k)$, where $P\subseteq Q=\{p_1,p_2,\dots ,p_r\}$, is a subdigraph of $G(n,k)$ induced on the set of vertices which are multiples of ${\prod }_{p_i\in P}{p}_i$ and are relatively prime to all primes $p_j\in Q\setminus P$. In this paper, we investigate the uniqueness of the factorization of trees attached to cycle vertices of the type $0$, $1$, and $(1,0)$, and in general, the uniqueness of $G(n,k)$. Moreover, we provide a necessary and sufficient condition for the isomorphism of the fundamental constituents $G_P^{\ast }(n,k_1)$ and $G_P^{\ast }(n,k_2)$ of $G(n,k_1)$ and $G(n,k_2)$ respectively for $k_1\ne k_2$.