On the tree structure of the power digraphs modulo $n$

Sawkmie, Amplify ; Singh, Madan Mohan

Czechoslovak Mathematical Journal, Tome 65 (2015) no. 4, pp. 923-945.

Résumé

For any two positive integers $n$ and $k \geq 2$, let $G(n,k)$ be a digraph whose set of vertices is $\{0,1,\ldots ,n-1\}$ and such that there is a directed edge from a vertex $a$ to a vertex $b$ if $a^k \equiv b \pmod n$. Let $n=\prod \nolimits _{i=1}^r p_{i}^{e_{i}}$ be the prime factorization of $n$. Let $P$ be the set of all primes dividing $n$ and let $P_1,P_2 \subseteq P$ be such that $P_1 \cup P_2=P$ and $P_1 \cap P_2= \emptyset $. A fundamental constituent of $G(n,k)$, denoted by $G_{P_2}^{*}(n,k)$, is a subdigraph of $G(n,k)$ induced on the set of vertices which are multiples of $\prod \nolimits _{{p_i} \in P_2}p_i$ and are relatively prime to all primes $q \in P_1$. L. Somer and M. Křížek proved that the trees attached to all cycle vertices in the same fundamental constituent of $G(n,k)$ are isomorphic. In this paper, we characterize all digraphs $G(n,k)$ such that the trees attached to all cycle vertices in different fundamental constituents of $G(n,k)$ are isomorphic. We also provide a necessary and sufficient condition on $G(n,k)$ such that the trees attached to all cycle vertices in $G(n,k)$ are isomorphic.

Détail

DOI : 10.1007/s10587-015-0218-x

Classification : 05C05, 05C20, 11A07, 11A15, 68R10
Keywords: congruence; symmetric digraph; fundamental constituent; tree; digraph product; semiregular digraph