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

Sawkmie, Amplify; Singh, Madan Mohan

Rendiconti del Seminario Matematico della Università di Padova, Tome 140 (2018), pp. 185-219.

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,...,n-1\}$ and for which there exists a directed edge from $x$ to $y$ if $x^k\equiv y(modn)$. 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^{*}(n,k)$, where $P\subseteq Q=\{p_1,p_2,...,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^{*}(n,k_1)$ and $G_P^{*}(n,k_2)$ of $G(n,k_1)$ and $G(n,k_2)$ respectively for $k_1\ne k_2$.

Classification : 05, 11
Mots clés : Power digraph, direct product, uniqueness of factorization, Chinese remainder theorem