On the tree structure of the power digraphs modulo \(n\). (English) Zbl 1363.11002

Summary: 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 [Czech. Math. J. 61, No. 2, 337–358 (2011; Zbl 1249.11006)] 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.


11A07 Congruences; primitive roots; residue systems
05C05 Trees
05C20 Directed graphs (digraphs), tournaments
11A15 Power residues, reciprocity


Zbl 1249.11006
Full Text: DOI Link


[1] G. Deng, P. Yuan: On the symmetric digraphs from powers modulo n. Discrete Math. 312 (2012), 720–728. · Zbl 1238.05104 · doi:10.1016/j.disc.2011.11.007
[2] J. Kramer-Miller: Structural properties of power digraphs modulo n. Mathematical Sciences Technical Reports (MSTR) (2009), 11 pages, http://scholar.rose-hulman.edu/mathmstr/11 .
[3] M. Křížek, F. Luca, L. Somer: 17 Lectures on Fermat Numbers: From Number Theory to Geometry. CMS Books in Mathematics/Ouvrages de Mathematiques de la SMC 9, Springer, New York, 2001.
[4] L. Somer, M. Křížek: The structure of digraphs associated with the congruence x k y (mod n). Czech. Math. J. 61 (2011), 337–358. · Zbl 1249.11006 · doi:10.1007/s10587-011-0079-x
[5] L. Somer, M. Křížek: On symmetric digraphs of the congruence x k y (mod n). Discrete Math. 309 (2009), 1999–2009. · Zbl 1208.05041 · doi:10.1016/j.disc.2008.04.009
[6] L. Somer, M. Křížek: On semiregular digraphs of the congruence x k y (mod n). Commentat. Math. Univ. Carol. 48 (2007), 41–58.
[7] B. Wilson: Power digraphs modulo n. Fibonacci Q. 36 (1998), 229–239. · Zbl 0936.05049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.